Proof: two vertices of equal degrees

Theorem

Let $G = (V, E)$ be a finite simple graph (undirected without loop) with at least two vertices, $V$ the set of vertices and $E$ the set of edges. The degree of a vertex $v$ is the number of edges adjacent to $v$.

G has at least two vertices of equal degree.

Proof

We will prove the theorem by contradiction.

Let $v \in V$, we note $n = |V|$ the number of vertices.

According to the degree theorem of a vertex, we have $0 \leq deg(v) \leq n-1$.

Let’s suppose by contradiction that all the vertices of G have different degrees.

The set of degrees $D$ of the vertices is therefore:

$D = \{0,1,2, \ldots, n-1\}$

However, this graph cannot have a vertex of degree $n-1$ and one of degree $0$.

Indeed, let’s suppose that a vertex $u$ exists such that $deg(u) = n-1$. Then $u$ must be connected to $n-1$ other vertices.

Let’s take for example a graph of 2 vertices. We have $D = \{0,1\}$, but if $v_1$ has an edge, $v_1$ is necessarily connected to $v_2$, but $v_2$ must not have an edge to have a different degree than $v_1$. Contradiction.

We therefore have either:

• $D = \{0,1,2, \ldots, n-2\}$
• $D = \{1,2, \ldots, n-1\}$

Such that $|D| = n-1$.

By the pigeonhole principle, we have |V| = n and |D| = n-1, so there are at least two vertices of equal degree.