100 vertex graph has a specific pair of vertices.

Question

Let $G$ be a simple graph with 100 vertices. Let us call the vertex $C$ uniform for $A$ and $B$ if it is either adjacent to both, either not adjacent to both.

Prove that there exists such pair of vertices that this pair has no less than 50 uniform vertices.

I have almost found the answer, I think, but the final step is hard to me.

There are ${100}\choose{2}$ pairs of vertices

Lemma: any vertex is uniform for $\geq {{50}\choose{2}} + {{49}\choose{2}} $ pairs of vertices.

Let a vertex A have $x$ adjacent and $99-x$ non-adjacent vertices. That means that A is uniform to ${{x}\choose{2}} + {{99-x}\choose{2}}$ vertices. The minimum is obtained at integer $x = 49, 50$. $\square$

Lemma: If the sum of degrees for a pair of vertices is even, then it can't have 49 uniform vertices. (The proof is easy.) There are $\geq \frac{49 \times 100}{2}$ pairs with even sum of degrees.

Adjacency doesn't affect evency of sum of degrees, because the conecting edge is counted twice. Every uniform vertex doesn't affect evency. So we see that there should be even amount of not-uniform vertices, so there should be even amount of uniform vertices as well. $\square$

That means that there exists a pair of vertices that

$\geq \frac{({{50}\choose{2}} + {{49}\choose{2}})\cdot 100}{{100}\choose{2}} = 48.5(05)$ uniform vertices.

Here I take the number of vertices, multiply it by the number of pairs they are uniform to and divide by the number of pairs, This gives the least average amount of uniform vertices per every pair.

How can I make the estimate better? (may be with the help of Lemma 2.)

(Thanks for parts of the proof to Nikita Gladkov and Grigory Yurgin)

Answer 1

I think I have got an answer. Let us propose by contradiction that there isn't any pair that we need, that means by Lemma 2 that any even pair has at most 48 uniform vertices. Let us consider $\frac{240100 - 48 x}{4950 - x}$

$x$ here is the amount of pairs with even sum of degrees.

If we have $a$ vertices with even degree, then the amount of even pairs is equal to. $x = a\cdot\left(a-1\right)\ +\left(100-a\right)\cdot\left(99-a\right)$

This parabola always $\geq 4900$

Using Desmos to look at the function, we see, that the function is $\geq 98$ if $x \geq 4900$ That gives the proof.

Answer 2

With an averaging I can get only $49$, not $50$. Make a new bipartite graph $G^*$ with pairs of vertices of $G$ on one side and with vertices of $G$ on the other side. Connect in $G^*$ every pair $u,v$ with vertex $w$ iff $w$ is connected or not connected to both of them in $G$. If a vertex in $G$ has a degree $d$ (and let $d'= 99-d$) then it is connected in $G^*$ with $$d^*={d\choose 2}+{d'\choose 2} = {d^2+d'^2-(d+d')\over 2} \geq {{1\over 2}(d+d')^2-(d+d')\over 2} $$ pairs, so since $d^*$ is an integer we have $d^*\geq 2401$.

On the other side if each pair has degree at most $48$ we have $${100\choose 2}\cdot 48 \geq 100\cdot 2401$$ which does not hold. So the minimum is at least $49$.