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