Question

Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?

• A. No two vertices have the same degree
• B. At least two vertices have the same degree
• C. At least three vertices have the same degree
• D. All vertices have the same degree

Answer 1

The correct option is B At least two vertices have the same degree

In a simple connected undirected graph (with more than two vertices), at least 2 vertices must have same degree, since if this is not true, then all vertices would have different degrees. A graph with all vertices having different degrees is not possible to construct (can be proved as a corollary to the Havell-Hakimi theorem). Notice that it is possible to construct graphs satisfying choices a, c and d.