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 K4 . Now only one option (C) left .
So, answer should be (C). But I don't know how to prove it.
@Arjun sir, i haven't got my consignment. the ...
Nice to see your plenty ...
For those who knows only about ...