Consider $G = (V,E)$. We want to prove that there is exist two vertices $v_1$ and $v_2$ and $\bar{V} : \forall v \in \bar{V}$ simultaneously connected or disconnected with $v_1$and $v_2$ and $|\bar{V}| \ge n/2$.
My attempt :
Induction with respect to $n$.
$n = 4$ and $n = 5$ are evident cases.
Now suppose it's true for $k \le n$.
Let's prove it for $k = n + 2$. We want to show that there is exists $v_1$ and $v_2$ and $1+\frac{n}{2}$ other vertices with given property.
Lets consider graph with $n$ vertices and add two new ones $u_1$ and $u_2$. As we know for any graph with $k = n$ vertices we have $v_1$ and $v_2$ and $\bar{V}$ with our rule. Then there are several cases:
$1)$ $u_1$ or $u_2$ connected or disconnected with $v_1$ or $v_2$. Then everything's good.
$2)$ $u_1 \sim v_1$ and $u_2 \sim v_2$ and $|\bar{V}| = n/2$ (if there was at least $n/2 + 1$ vertices the rule would be performed). That's bad case and we should think about it.
I thought in such direction: let's delete $v_1$ and $v_2$. Now we have graph $G' = (V-(v_1 + v_2) , E') $ with $n$ vertices for which we know that there are $z_1$ and $z_2$ and $\tilde{V}$ with $n/2$ vertices (if there was at least $n/2 + 1$ we would get $v_1$ and $v_2$ back and problem would be solved). If $z_1$ or $z_2$ $\in \bar{V}$ then everything's okay because if we return $v_1$ and $v_2$ some of $z_1$ or $z_2$ would be simultaneously connected or disconnected with $v_1$ and $v_2$. So again we have bad case $z_1 \sim v_1$ and $z_2 \sim v_2$. That's the place I got stuck.
Maybe I go wrong way and there is more elegant solution? Any hints would be be good.
Let $S(v_1,v_2)=\{w|\{w\text{ is adjacent to both }v_1,v_2 \text{ or w is adjacent to neither } v_1 \text{ nor }v_2\}$. The goal is to show that there exists a pair of vertices for which $|S(v_1,v_2)| \geq \dfrac{n}{2}$.
We can show that the average value of $|S(v_1,v_2)|$ over all pairs $(v_1,v_2)$ is high and conclude that there is a pair with $|S(v_1,v_2)|$ at least $\dfrac{n-1}{2}$ when $n$ is odd and at least $\dfrac{n}{2}+1$ when $n$ is even. [Perhaps the even case can be used to obtain $\dfrac{n}{2}$ for the odd case as well.] For this, we consider the sum over all pairs.
Let $T=\sum_{v_1,v_2} |S(v_1,v_2)|=\sum_{v_1,v_2}\sum_{w \in S(v_1,v_2)} 1$.
Now we reverse the order of summation, that is for each $w$, count the number of pairs $\{v_1,v_2\}$ for which it is adjacent to both of them or adjacent to neither of them, and finally sum over all $w$.
The count for $w$ is $\dbinom{d(w)}{2}+\dbinom{n-1-d(w)}{2}$, where $d(w)$ is the degree of $w$.
Thus, $T= \sum_{w}\dbinom{d(w)}{2}+\dbinom{n-1-d(w)}{2}$. The minimum value of $\dbinom{x}{2}+\dbinom{n-x}{2}$ is $2\dbinom{n/2}{2}$ if $n$ is even and $\dbinom{n-1}{2}+\dbinom{n+1}{2}$ if $n$ is odd.
We consider the case that $n-1$ is even. We have, by the preceding argument: $T \geq 2n\dbinom{(n-1)/2}{2}=\dfrac{n(n-1)(n-2)}{4}$. Dividing by $\dbinom{n}{2}$, we obtain that the average value of $|S(v_1,v_2)|$ is at least $\dfrac{(n-2)}{2}=\dfrac{n}{2}-1$, but since $n$ is odd, there must be a pair with value at least $\dfrac{n-1}{2}$.
Now consider the case that $n-1$ is odd. We have: $T \geq n\left(\dbinom{n-1}{2}+\dbinom{n+1}{2}\right)=\dfrac{n^3}{4}$. Dividing by $\dbinom{n}{2}$, the average value is at least $\dfrac{n^2}{2(n-1)} \geq \dfrac{n+1}{2}$, and since $n$ is even, there must be a pair with value at least $\dfrac{n+2}{2}$.