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)

  • $\begingroup$ Is the graph connected? $\endgroup$ – vidyarthi Apr 3 at 6:38
  • 1
    $\begingroup$ @vidyarthy If the graph is not connected and one connectivity component has more then 1 and less then 50 vertices then there is a pair of vertices in this component that has uniform vertices in another connectivity components. If we have a lonely vertex in one component and another vertex with degree less then 50 then we are done also, I hope. $\endgroup$ – Lada Dudnikova Apr 3 at 6:40
  • $\begingroup$ How can you say that greater than $\binom{50}{2}+\binom{49}{2}$ pair of vertices have any vertex as uniform? And also how do you prove your second proposition that if sum of degrees of a pair of vertices is even, then it cannot have $49$ uniform vertices? Could you elaborate? $\endgroup$ – vidyarthi Apr 3 at 6:47
  • $\begingroup$ @vidyarthi, ok, will edit the question with the proof of these lemmas. $\endgroup$ – Lada Dudnikova Apr 3 at 6:49
  • 1
    $\begingroup$ @vidyartgi Edited. $\endgroup$ – Lada Dudnikova Apr 3 at 7:20

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.


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.