edited by
65,104 views
39 votes
39 votes

Which of the following statements is true for every planar graph on $n$ vertices?

  1. The graph is connected
  2. The graph is Eulerian
  3. The graph has a vertex-cover of size at most $\frac{3n}{4}$
  4. The graph has an independent set of size at least $\frac{n}{3}$
edited by

7 Answers

1 votes
1 votes
Clearly option (A) is wrong. Take $n$ isolated vertices. They are planar and they are not connected!

Clearly option (B) is wrong. Take $K_{1,3}$ which is non Euler because not all vertices have even degree [rather no vertices have even degree] but it can be drawn as a plane graph.

Also option (D) is wrong. Take $K_4$. For any complete graph, there is only one possible size of independent set of vertices which is $1$, Because each pair of vertices are adjacent. But option (D) says that we should have an independent set of size at least $\frac{4}{3} = 1.33$ or at least $2$.

So (C) is the correct option. Let’s see why.

 

$\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} \tag 4$$

[The above result in $(4)$ simply states that we have maximum independent set of size at least $\frac{n}{4}$. Since we have a maximum independent set of size at least $\frac{n}{4}$ we can say that we have “an independent set” (i.e. “$\exists$ an independent set”) of size at least $\frac{n}{4}$. But this does not prove option (D) wrong!! There might be an independent set of size at least $\frac{n}{3}$ even if $\alpha(G)\geq\frac{n}{4}$. Who knows? So the counter-example was necessary]

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}$$

Since we have a minimum vertex cover of size at most $\frac{3n}{4}$, we indeed have “a vertex cover” of size at most $\frac{3n}{4}$.
0 votes
0 votes

The answer has to be option A  reason being that all planar graphs are connected.

Option B is clearly false.

Option C is false as vertex cover of planar graph <= floor value( 3n/4 )

option D is also false as the independent set has size ceil value( n/3 )

Answer:

Related questions

31 votes
31 votes
4 answers
1
makhdoom ghaya asked Nov 27, 2016
7,821 views
Which of the following graphs is/are planar?
33 votes
33 votes
9 answers
3
makhdoom ghaya asked Feb 13, 2015
24,603 views
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
17 votes
17 votes
2 answers
4
go_editor asked Sep 29, 2014
7,029 views
K4 and Q3 are graphs with the following structures.Which one of the following statements is TRUE in relation to these graphs?K4 is a planar while Q3 is notBoth K4 and Q3 ...