How to proof that a graph of order $n$, $n\geq 2$ has two vertices of the same degree?
Asked
Active
Viewed 7,730 times
1
-
2Hint: suppose they all have different degrees. The possible degrees are $0,1,\ldots,n-1$. – Théophile Nov 18 '16 at 15:24
-
1Hint: use the pigeonhole principle. – Yuxiao Xie Nov 18 '16 at 15:24
1 Answers
10
Let G be any finite simple graph with more than one vertex and $|V_G|$ = n ≥ 2. First, we notice that the maximal degree of any vertex in G is less than equal n − 1. Also, if our graph G is not connected, then the maximal degree is strictly less than n − 1. 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.