GATE CS 2008 Q23 — Graphs: Connectivity, Matching, Colouring

We can evaluate each option to find the correct statement for any planar graph on $n$ vertices:

• Option A (The graph is connected): False. A planar graph can be disconnected. For example, a graph with $n$ vertices and no edges is planar but disconnected for $n \ge 2$.
• Option B (The graph is Eulerian): False. A graph is Eulerian if and only if every vertex has an even degree and all its vertices with non-zero degree belong to a single connected component. A simple path graph $P_3$ is planar but has vertices of degree 1, so it is not Eulerian.
• Option D (The graph has an independent set of size at least $\frac{n}{3}$): False. Consider the complete graph $K_4$, which is planar. For $K_4$, the number of vertices is $n = 4$. The size of its maximum independent set is $1$. However, $\frac{n}{3} = \frac{4}{3} \approx 1.33$. Since $1 < 1.33$, this statement does not hold.
• Option C (The graph has a vertex-cover of size at most $\frac{3n}{4}$): True.
  • By the Four Color Theorem, any planar graph is $4$-colorable. This means the vertices can be partitioned into $4$ independent sets.
  • By the Pigeonhole Principle, at least one of these independent sets, say $I$, must contain at least $\frac{n}{4}$ vertices (i.e., $|I| \ge \frac{n}{4}$).
  • Since the complement of any independent set is a vertex cover, the set $V \setminus I$ is a valid vertex cover.
  • The size of this vertex cover is: $$|V \setminus I| = n - |I| \le n - \frac{n}{4} = \frac{3n}{4}$$
  Thus, every planar graph has a vertex cover of size at most $\frac{3n}{4}$.