I'm trying to figure out how to prove that an undirected graph with $n\geq$ 2 vertices has at least $2$ vertices with the same number of degrees, no matter how the edges are distributed. The statement is obvious, but I don't know how to prove it. My attempts led me to the pigeonhole principle, but I could not figure out how to use it correctly. Any hint would be very helpful to me. Thanks!
Asked
Active
Viewed 24 times
