Pigeon hole principle for Graphs

Question

There is a Simple Graph G with 10 vertices and 28 edges. I need to show that there exist two vertices whose sum of degrees is at least 12.

My attempt:

The sum of all the degrees of vertices must be 28*2 = 56. I understand that we should use pigeon hole principle to proceed but I have no idea what to take as pigeons and what to take as pigeon holes. Kindly please help on how I can proceed further.

Answer 1

This can be solved by pure pigeonhole principle, though it's a bit tricky.

There are $45$ pair of vertices $(i, j)$. Let $d_{i, j}$ be the sum of degrees of vertices $i$ and $j$.

When we add one edge, the sum of $d_{i, j}$ will be increased by $18$. For example, when we add edge $1-2$:

• $d_{1, 2}$ will be increased by $2$,
• $d_{1, 3}, d_{1, 4}, \dots, d_{1, 10}$ will be increased by $1$, and
• $d_{2, 3}, d_{2, 4}, \dots, d_{2, 10}$ will be increased by $1$.

Therefore, if we add $28$ edges, the sum of $d_{i, j}$ will be $18 \times 28 = 504$. Then, it can be translated into this scenario:

There are $45$ holes and $504$ pigeons inside these holes. Show that at least one hole has $12$ or more pigeons.

This is true by pigeonhole principle, because $\lceil 504/45 \rceil = 12$.