$\text{Which of the following statements is true for every planar graph on $n$ vertices?}$
- $\text{ The graph is connected}$
- $\text{ The graph is Eulerian}$
- $\text{ The graph has a vertex-cover of size at most $\frac{3n}{4}$}$
- $\text{ The graph has an independent set of size at least $\frac{n}{3}$}$ $$\tag {GATE CS 2008}$$
Clearly options 1 and 2 are wrong. I made an attempt to check the correctness of option 3 and 4.
$\alpha(G) : \text{Independence Number of G}$
$\beta(G) : \text{Minimum vertex cover of G}$
$n(G): \text{Number of vertices of G}$
$\chi(G): \text{Chromatic Number of G}$
We know,
$$\alpha(G)+\beta(G)=n(G) \tag 1$$
We also know from $\text{Four color theorem}$,
For a planar graph, $$\chi(G) \leq 4 \tag 2$$
Now we also know that,
$$\frac{n(G)}{\alpha(G)}\leq \chi(G)\tag 3$$
From $(2)$ and $(3)$ we have,
$$\frac{n(G)}{\alpha(G)}\leq \chi(G) \leq 4 \implies \frac{n(G)}{\alpha(G)} \leq 4 \implies \alpha(G)\geq \frac{n(G)}{4} = 0.25 \times n(G) \tag 4$$
Adding $\beta(G)$ to both sides of $(4)$, we have,
$$\alpha(G)+\beta(G)\geq \frac{n(G)}{4} + \beta(G)$$
But from $(1)$, we have
$$n(G)\geq \frac{n(G)}{4} + \beta(G) \implies \beta(G)\leq \frac{3n}{4} \tag 5$$
But to show that graph has an independent set of size at least $\frac{n}{4}$, we should try to show that the minimum size of the independent set is at least $\frac{n}{4}$ but I have shown it for $\alpha(G)$ which is the maximum size of the independent set.
Also to show that $G$ has a vertex-cover of size at most $\frac{3n}{4}$ I guess I need to show that the maximum vertex cover is at most $\frac{3n}{4}$, but what I have shown is the bound for $\beta(G)$ which the minimum vertex cover.
I am kind of stuck. How to proceed. Please guide. Thank you.
Four-colour the graph. The vertices with the three rarest colours are a covering set.