Let $G$ be a simple graph with $n$ vertices, where $n \ge 2$. Prove that $G$ has two vertices $u$ and $v$ with $d(u) = d(v)$.
Hint: if $G$ is nonempty, consider $G — e$ where $e$ is an edge of $G$, and use induction on the number of edges of $G$.
I am confused on where to start off this problem using the hint my book has given me. I saw a way to do this proof using pigeonhole principle but I have not learned that in my class yet. If someone could show me where I would start induction in this problem or just an idea of where to start. I'd be grateful.
Say that degrees of vertices are all different. Since each degree is at most $n-1$ and at least 0 then since we have $n$ vertices, these degrees must take all possible values beetwen 0 and $n-1$. Specialy there is vertex A with degree 0 and vertex B with degree $n-1$. But then B must be connected with each vertex and also with A. But then A can't have degree 0. A contradiction.