Which of the following statements is true for every planar graph on $n$ vertices?
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.
Planar graph not necesarily be connected. So option (A) is false. Options (B) and (D) can be proven false with the example of K4 . Now only one option (C) left .
So, answer should be (C). But I don't know how to prove it.
That is google form link. You may try ...