Which one of the following is TRUE for any simple connected undirected graph…

Answer: At least two vertices have the same degree.

Proof (pigeonhole principle):

• Let n be the number of vertices, with n > 2.

• Because the graph is simple and connected, each vertex degree is at least 1 and at most n-1. So the possible degree values are 1, 2, ..., n-1 (a total of n-1 distinct values).

• There are n vertices but only n-1 possible degree values, so by the pigeonhole principle at least two vertices must have the same degree.

Why the other statements fail (brief counterexamples):

• The statement that no two vertices have the same degree is false: a path on 3 vertices has degrees {1, 1, 2}, so two vertices share degree 1.

• The statement that at least three vertices have the same degree is not guaranteed: a path on 4 vertices has degrees {1, 2, 2, 1}, where only pairs of vertices share degrees, not three.

• The statement that all vertices have the same degree is also not always true; many connected graphs are not regular (for example, the path on 3 vertices above).