Which of the following statements is true for every planar graph on $n$ vertices?
Planar graph not necesarily be connected. So option (A) is false. Options (B) and (D) can be proven false with the example of K_{4 }. Now only one option (C) left . So, answer should be (C). But I don't know how to prove it.
Independent Set ≥ ceil(n/k) where, n is the number of vertices and k is the chromatic number For any planar graph k ≥ 3 and k ≤ 4, therefore, the Independent set is at least ceil(n/4). Hence (D) is false. Now we know that Vertex cover + Independent Set Number =n. If Independent set ≥ ceil(n/4) then, Vertex cover ≤ n - (n/4) Vertex Cover ≤ 3n/4 Vertex Cover is at most 3n/4. So (C) is the correct answer.
Gatecse