Which of the following statements is true for every planar graph on n vertices? A. The graph is connected B. The graph is Eulerian C. The graph has a vertex-cover of size at most 3n/4 D. The graph has an independent set of size at least n/6

GATE 2008 · Discrete Mathematics · Graph Planarity · medium

Answer: The graph has a vertex-cover of size at most 3n/4.

1. Apply the Four Colour Theorem: Since every planar graph is 4-colourable, its n vertices are partitioned into at most 4 independent sets. By the pigeonhole principle, the largest set has size at least n/4. So alpha(G) >= n/4.
2. Apply Gallai's identity to get the vertex-cover bound: Since alpha(G) >= n/4, we have tau(G) = n - alpha(G) <= n - n/4 = 3n/4. So every planar graph has a vertex cover of size at most 3n/4.