If $G$ is a simple graph with at least two vertices, prove that $G$ must contain two or more vertices of the same degree

Question

If $G$ is a simple graph with at least two vertices, prove that $G$ must contain two or more vertices of the same degree.

I proved this theorem, I need to check if my proof is correct.

---

Base case: Let $V(G)=\{v_1,v_2\}$, then the most edges the graph can have is $\frac{2(2-1)}{2}=1$, so this means $E(G)=\{v_1 v_2\}$, and $deg.v_1 = deg.v_2=1$

Inductive hypothesis: Let $V(G) = \{ v_1, ..., v_k \} | k > 2$, then the most edges this graph can have is $\frac{k(k-1)}{2}$, so this means $E(G)=\{e_1, ..., e_{\frac{k(k-1)}{2}}\}$. Suppose $deg.v_i=deg.v_j|i≠j∧v_i,v_j∈V(G)$

Inductive step : Let $V(G) = \{ v_1, ..., v_k, v_{k+1} \}$, then the most edges this graph can have is $\frac{(k+1)k}{2}$, which means that $E(G)=\{e_1, ..., e_{\frac{(k+1)k}{2}}\}$, and that there are $\frac{(k+1)k}{2}-\frac{k(k-1)}{2}=k$ new edges, each one coming from $v_1,...,v_k$ vertices, which mans that each vertex's degree is increased by one, and, since $deg.v_i=deg.v_j$ is true, $deg.v_i+1=deg.v_j+1$ is also true, which comples the proof.

---

The only thing that kinda' makes me doubt about the correctness of the proof, is that I always set the number of edges to the highest possible, and I don't know if this breaks the proof's generality.

Thanks in advance.

Answer 1

Here you can find two beautiful proofs, one is direct, the other is by induction

https://www.gottfriedville.net/mathprob/graph-samedeg.html

Direct Proof

(By Andrew Hughes) If all the degrees of a graph of n vertices are different, they must be exactly, {0, 1, 2, ...., n-1}. But it is impossible to have a vertex of degree 0 (connected to no other vertex) and one of degree n-1, (connected to every other vertex) simultaneously.

Thus there is no such graph.

Induction Proof

A graph with 2 vertices has either 0 or 1 edges, and in either case, the two nodes have the same degree.

Assume the theorem holds for k vertices and there are two (or more) of same degree.

The existing k vertices have at most (k-1) different degrees 0,1,2, ...., k-1 (with at least one missing, and at least one pair). [ by induction hypothesis ]

Add another node and, one by one, its edges.

If it stays degree 0, whatever existing pairs there were remain.

When the first new edge is added, the new node has degree 1, and we have one of the following possibilities:

1) connected to a node with a unique degree: An existing pair of vertices with equal degrees remains intact.

2) connected to a member of a pair of same degree. 2a) if there is another pair, that pair remains. 2b) if this was the only pair, let it be degree d and before we added this edge, the list of degrees was 0, 1, 2, ..., d-1, d , d, d+1, d+2, .... k-1 with one element missing.

2b.i) d+1 was missing: Now we have a pair of 1's. 2b.ii) Some other degree was missing: Now we have a pair of d+1's.

This is the situation for each new edge added, but a different constant instead of 1 as the degree of the new node increases.

Therefore, there is always a pair.

Answer 2

Your base case proof is lacking. Yes, it's true, the graph can have at most one edge, and if it has one edge, then it has two vertices of the same degree.

But you didn't prove yet that all graphs with two vertices have at least two vertices of the same degree. You don't know that the graph has one edge - it might have a different number of edges.

The mistake may be minor, but it still needs correcting.

---

Next, your inductive hypothesis is wrong. It should say $k\geq 2$, not $k>2$.

---

Next, while the graph in the inductive hypothesis can have at most $\frac{k(k-1)}{2}$ edges, it doesn't have to have that many edges. It can have fewer edges. So $E(G)$ is wrong in the inductive hypothesis.

---

The same mistake is made in the inductive step. There aren't necessarily $k$ new edges. There could be fewer.

Answer 3

I don't think (direct) induction is the most intuitive way to go about this. I would go for the pigeonhole principle. There are $n$ vertices, and $n$ different degrees any vertex may possibly have (from $0$ to $n-1$). By itself, this doesn't show anything. But once we note that the lowest possible degree and the highest possible degree cannot both be present, the principle kicks in, and there must be some degree which two vertices share.