# Prove that any simple graph with more than one vertex has at least two vertices with the same degree

I have to show that a finite simple graph with more than one vertex has at least two vertices with the same degree. Then, the question is if this is also true for graphs with loops.

My solution:

If G is a simple graph with more than one vertex and $|VG| = n ≥ 2$ we can discuss two different cases:

Case 1: Assume that G is connected. We can not have a vertex of degree $0$ in G, so the set of vertex degrees is a subset of $S = {1, 2, · · · , n − 1}$. Since the graph G has n vertices, by pigeon-hole principle we can find two vertices of the same degree in G.

Case 2: Assume that G is not connected. G has no vertex of degree $n − 1$, so the set of vertex degrees is a subset of $S′ = {0, 1, 2, · · · , n − 2}$. By pigeon-hole principle again, we can find two vertices of the same degree in G.

Now, I have few examples in my head that can prove that we can't say the same for the graphs with loops but how can I explain that?

Thank you.

• By 'loop' you mean that there can be an edge from a vertex to itself? Commented Jun 6, 2017 at 20:56
• Yes, exactly. :) Commented Jun 6, 2017 at 20:57
• OK, then a simple counterexample will do! Commented Jun 6, 2017 at 21:02

If you already have a counterexample, just state it to disprove the claim. For example the graph with adjacency matrix $$\begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix}$$