edited by
56,638 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

Best answer
37 votes
37 votes

Independent Set $\geq$ $\large \left \lceil \frac{n}{k} \right \rceil$ where,
$n$ is the number of vertices and $k$ is the chromatic number 
For any planar graph, $k \geq 3$ and $k \leq 4$, therefore, the Independent set is at least $\lceil n/4 \rceil$.
Hence (D) is false.

Now we know that size of Vertex Cover + Independent Set Number $=n$.
If Independent set number $\geq  \lceil n/4 \rceil$ 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.

edited by
18 votes
18 votes

A) Incorrect. Consider the following disconnected planar graph:

 

B) Incorrect. A graph is Eulearian if all vertices have even degree but a planar graph can have vertices with odd degree .

 

C) Correct. Any planar graph can be vertex colored with maximum 4 colors (4-color theorem) so that no two adjacent vertices have same color.

So consider a planar graph with n vertices having chromatic number 4. So atmost we have 4 set of vertices of each color having size n/4 (evenly distributed). If we remove a set, we still will have all the vertices which is atleast one of the endpoint of all the edges i.e. we have a vertex cover having size n-(n/4) = 3n/4.

 

D) Incorrect. Consider K4 graph. It has independent set size 1 which is less than 4/3.

12 votes
12 votes

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.

Answer:

Related questions

31 votes
31 votes
4 answers
1
makhdoom ghaya asked Nov 27, 2016
7,720 views
Which of the following graphs is/are planar?
32 votes
32 votes
9 answers
3
makhdoom ghaya asked Feb 13, 2015
24,370 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
6,931 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 ...