Which of the following statements is true for every planar graph on $n$ vertices?
Independent Set $\geq$ ceil$(n/k)$ where, $n$ is the number of vertices and $k$ is the chromatic number For any planar graph $k \geq 3$ and $k \geq 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 $\geq$ ceil$(n/4)$ then, Vertex cover $\leq n - (n/4)$ Vertex Cover $\leq 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 K_{4 }. Now only one option (C) left . So, answer should be (C). But I don't know how to prove it.
Gatecse
@Arjun sir, i haven't got my consignment. the ...
@Manish1
Nice to see your plenty ...
For those who knows only about ...