- #1
Robben
- 166
- 2
Homework Statement
Show that any finite graph contains two vertices lying on the same number of edges.
Homework Equations
None
The Attempt at a Solution
I am confused how my book proved this.
Let G be a graph with n vertices ##v_1, ..., v_n.## Place ##v_i## in a pigeonhole labelled ##m## if it has exactly ##m## neighbours. The possible labels on the pigeonholes are ##0,1,2,..., n-1## so ##n## vertices are placed in ##n## pigeonholes. However, the pigeon-holes labelled ##0## and ##n-1## cannot both be occupied.
Why can't they both not be occupied? And what exactly do they mean by occupied?