GATE CSE 2008 | Question: 23

Question

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

• A. The graph is connected
• B. The graph is Eulerian
• C. The graph has a vertex-cover of size at most $\frac{3n}{4}$
• D. The graph has an independent set of size at least $\frac{n}{3}$

Comments

the option C said that the vertex cover size cannot be greater than 3n/4

but when I took n=8 in worst case the vertexcover size came out to be 7

which is > 3*8/4.

What's wrong here?

---

@Nandkishor3939 that's not vertex cover whatever you've written. One possible vertex cover for your example is $A = \{a, c,e,g\}$ where $|A| \leq 7$

---

You are representing Independent vertex set no. with Apha and Vertex covering no. with Beta. But I think it should be other way around.

Answer 1

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.

Comments

The size of the least Independent set is the set of single vertices, i.e 1.

Ex: If V : { a, b, c, d, e, f }

{a}

{b}

... are all independent sets

Source : https://www.youtube.com/watch?v=ST1ozPWvgjs 

---

For every planar graph, there is an independent set of size AT LEAST n/4 . Yes, there is also an independent set of size at least 1 but both these statements aren't contradictory.

For the vertex cover, we're missing the "there exists" part. THERE EXISTS a vertex cover of size at most 3n/4. Although, we can take a vertex cover with all the vertices  as well, so there is also a vertex cover of size n. Hence these are also are not contradictory.

---

How k<=3 ,k can also be 2 in case of a square and its planar

Answer 2

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.

Answer 3

Planar graph not  necesarily be connected. So option (A) is false. Options (B) and (D) can be proven false with the example of K₄ . Now only one option (C)  left  .

So, answer should be (C). But I don't know how to prove it.

Comments

We can prove C using every planar graph is 4 colourable.

---

A wheel with 7 vertices is counter example for option D.

The independent set can consist of centre vertex which alone forms an independent set, whose size is 1. (given size is atleast n/3, here 7/3 = 2).So it is wrong.

Is this right?

---

you can also take any example of wheel graph with vertices greater 6 u should take 6

all have independence set 1

Answer 4

It's a consequence of the four color theorem. Take a planar graph G, and color it in 4 colors. All vertices except the ones in the color class of greatest size form a vertex cover consisting of at most 3n/4 vertices.

 

https://math.stackexchange.com/questions/1063860/proving-every-planar-graph-have-vertex-cover-of-size-of-at-most-3n-4