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.
Best Answer
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}$$