GATE CS 2009 Q3 — Graphs: Connectivity, Matching, Colouring

To find the correct statement for any simple connected undirected graph $G = (V, E)$ with $n$ vertices (where $n > 2$), we can use the Pigeonhole Principle.

1. Identify the possible degrees:

• In a simple graph with $n$ vertices, the maximum possible degree of any vertex is $n - 1$.
• Since the graph is connected and $n > 2$, there can be no isolated vertex (a vertex with degree $0$).
• Therefore, the possible degrees for any vertex must belong to the set: $$\{1, 2, 3, \dots, n - 1\}$$

2. Apply the Pigeonhole Principle:

• The number of available degree values (pigeonholes) is $n - 1$.
• The number of vertices (pigeons) is $n$.
• Since $n > n - 1$, by the Pigeonhole Principle, at least two vertices must share the same degree.

Counterexample for other options:

Consider a simple path graph $P_3$ with $3$ vertices ($v_1 - v_2 - v_3$):

• Degrees of the vertices are: $\text{deg}(v_1) = 1$, $\text{deg}(v_2) = 2$, and $\text{deg}(v_3) = 1$.
• This immediately disproves:
  • Option A: Two vertices ($v_1$ and $v_3$) have the same degree.
  • Option C: Only two vertices have the same degree, not three.
  • Option D: Not all vertices have the same degree.

Thus, Option B is always true.