Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices? A. No two vertic...

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.

Accepted Answer

At least two vertices have the same degree  (Option B) In a simple graph on n vertices every degree lies between 0 and n-1, giving n possible values. But degree 0 (isolated) and degree n-1 (joined to all) cannot both appear at once. So really only n-1 distinct degrees are usable for n vertices - by the Pigeonhole Principle two vertices must share a degree.