Pigeonhole principle

Proposition Statement

In any $graph$ $G$ of order $n \geq 2$ , there must be two distinct $vertices$ sharing the same $degree$ . This is the core claim of the proposition.

The proposition leverages the $pigeonhole principle$ , which in this context says you cannot assign $n$ vertices to $n$ different degrees in ${0, 1, \dots, n - 1}$ without a repeat.

Interpreting the degrees as “pigeonholes” and vertices as “pigeons” immediately suggests that at least two pigeons land in the same hole, i.e., two vertices have equal degree.

This result highlights a fundamental constraint on how degrees can be distributed in a finite $graph$ .

$Example$
In a path on $3$ vertices, the degrees are ${1, 2, 1}$ , so the two end vertices both have degree $1$ .

$Metaphor$
It’s like placing $3$ socks into $3$ boxes labeled $0, 1, 2$ where box $2$ ends up empty, forcing two socks into the same remaining box.

Proof by Contradiction

Assume, towards a $contradiction$ , that all $n$ vertices of $G$ have pairwise different $degrees$ .

Then the function

d_{G} : V (G) \to {0, 1, \dots, n - 1}

is injective, since no two vertices share the same degree.

But $| V (G) | = n$ equals the size of ${0, 1, \dots, n - 1}$ , so an injective map between two finite sets of equal size must also be surjective.

This sets up the contradiction, because the map cannot cover all degree values.

$Example$
If $G$ has $4$ vertices, an injective map to ${0, 1, 2, 3}$ would require using each degree exactly once.

$Metaphor$
It’s like trying to seat $4$ guests at $4$ chairs but insisting nobody sits in a particular chair; eventually someone must.

Injection Implies Surjection

Since $d_{G}$ is injective and both domain and codomain have size $n$ , it follows that

d_{G} (V (G)) = {0, 1, \dots, n - 1} .

Every degree value is achieved by some vertex.

In particular, there must be a vertex of degree $n - 1$ and a vertex of degree $0$ under this assumption.

This would mean one vertex connects to all others while another connects to none, coexisting in the same graph.

Such a scenario leads to an impossibility in any simple $graph$ .

$Example$
In a hypothetical $5$ -vertex graph, one vertex would have degree $4$ and another degree $0$ if all degrees $0$ – $4$ occur.

$Metaphor$
It’s like having a superstar who knows everyone at a party and a recluse who knows no one—yet they’re in the same tightly knit gathering.

The Impossibility of Surjection

If a vertex $v$ has degree $n - 1$ , it is adjacent to every other vertex in $G$ , so no vertex can have degree $0$ .

Hence $d_{G}^{- 1} (0) = \emptyset$ , contradicting surjectivity which demands some vertex of degree $0$ .

This contradiction nullifies the assumption that all degrees are distinct.

Therefore two vertices must share the same $degree$ , proving the proposition.

$Example$
In any simple $n$ -vertex graph, you cannot simultaneously have someone who shakes hands with everyone and someone who shakes hands with nobody.

$Metaphor$
You can’t have a universal celebrity and a complete hermit at the same small party without overlapping acquaintances.

Conclusion

By assuming all $n$ vertices have distinct degrees, we invoked the $pigeonhole principle$ to force injectivity and hence surjectivity of the degree map $d_{G}$ .

Surjectivity implies both a vertex of degree $n - 1$ and one of degree $0$ , which is impossible in a single simple $graph$ .

This $contradiction$ guarantees that at least two vertices must share the same $degree$ , completing the proof.