Verry nice problem! Solution: Induction on $|V|$, for $n=4$ the problem is trivial so we can assume it is true for $|V|$=$N$ and prove it for $|V|=N+1$ Since by removing a vertex from the graph the condition of the problem is still true le us assume that V has three parts, $K_1$ a complete graph, $K_2$ a complete disconnected graph and vertex $v$, if $v$ would be connected to every vertex of $K_1$ or disconnected to every vertex of $K_2$ the problem would be finished by adjoining $v$ to one of the sets $K_1$ or $K_2$, so let us assume that there exist the sets, $A_1$ included in $K_1$ of which $v$ is disconnected, and $A_2$ included in $K_2$ of which $v$ is connected, we call a vertex of $A_1$ good if it is disconnected to every vertex of $K_2$, and a vertex of $A_2$ good if it connected to every vertex of $K_1$, we call a vertex of $A_1$ or $A_2$ bad otherweise.If for example all the vertexes of $A_1$ are good we could move them to $K_2$ and put $v$ on $K_1$.Let us suppose that both $A_1$ and $A_2$ contain bad vertexes, let us call them $v_1$ and $v_2$ W.L.OG let us assume that the edge $v_1-v_2$ exists(the other case is the same) let $v_3$ be a vertex from $K_1$ wich is disconnected vrom $v_2$ (that maxes it bad).So by choosing the quadruple $v,v_1,v_2,v_3$ we obtain a contradiction with the statement so it is impossible for both the sets $A_1 , A_2$ to contain bad vertexes.

Croatian mathematical olympiad, day 1, problem 2 has posted before: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=401312 [Moderator: and the whereof use of the extremal element principle - considering the largest clique of friends - considerably shortens the proof.]