Project ForgeDiscrete Mathematics
Graph Theory
GATE 2009
Medium
Which one of the following is TRUE for any simple connected undirected graph with more than 2 vertices?
- ANo two vertices have the same degree.
- At least two vertices have the same degree.
- CAt least three vertices have the same degree.
- DAll vertices have the same degree.
Explanation
In a simple graph on n vertices, each vertex's degree lies in {0,...,n-1} — that's n possible values but n vertices, and a graph can't simultaneously have both a degree-0 and a degree-(n-1) vertex (the latter is connected to everyone, contradicting the former's isolation) when connected. This leaves at most n-1 usable degree values for n vertices, so by pigeonhole at least two vertices share a degree.
Source: GATE CS 2009 (2009)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.