Points connected to graph

18 Views Asked by At

I have $23$ points. Each pair of points has at most one edge connecting them.

For each of the $23$ points I add up each edge's degree. After doing the summation I get an integer $n$ such that $n \geq 207$.

How can I prove that there has to be some point that has a degree of at least $10$?

Does this have something to do with handshaking lemma?

1

There are 1 best solutions below

0
On BEST ANSWER

The sum of the degrees is just twice the number of edges, hence even, hence is in fact $\ge 208>207=9\cdot 23$. By pigeon-hole, one of the summands must be $>9$ (i.e., $\ge 10$, as desired).