The Gateway to Computer Science Excellence

+23 votes

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

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

+3

Shouldn't option C be like:

The graph has a **minimum** vertex-cover of size at most 3n/4.

Because each graph has a vertex-cover of size n, as set of all vertices is also a vertex cover.

+11

@Pratik, I also think the same. It should be minimum vertex cover and largest independent set.

Because if we consider 2 theorems , then answer will be valid in case of **minimum** vertex cover not vertex cover.

1) size of largest independent set + size of minimum vertex cover = no. of vertices

i.e. $\alpha(G) + \beta (G) = n$

2) $\alpha(G) \geq \frac{n}{\chi (G)}$

Since , for planar graphs , $\chi (G) \leqslant 4$ . So, $\frac{n}{\alpha (G)} \leqslant 4$. Therefore, $\frac{n}{4} \leqslant \alpha (G)$.

Now, Since, $\frac{n}{4} \leqslant \alpha (G)$. So, $\;\frac{n}{4} \leqslant (n-\beta(G))$. Therefore, $\beta(G) \leqslant \frac{3n}{4}$.

So, both things should be correct in case of** minimum** vertex cover and **largest** independent set not only vertex cover and independent set.

0

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?

0

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

+24 votes

Best answer

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 \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.

+1

I can't find any source for the formula for independent set$\geq \left \lceil n/k \right \rceil$. Please cite your source.

+12

@habedo, we can use our Intuition here.IF we can color a graph using $k$ colors then it means every set of $k$ vertices are dependent (or adjacent ) to each other so total size of independent set will be $n/k$

+11 votes

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

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

0

How is option D proved false with example of K4? K4 has an independent set of size 1 which is what you get by doing n/3 => 4/3 = 1.

0

For vertex cover of K4 size will be 2 maximal two edges would be sufficient to cover all vertices here and according to formula it would be less than or equal to (3*4)/4 equals to 3 bt how size of vertex cover would be 3 not getting it 2 becoz in that case it wouldn't be maximal set

+10 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.

52,345 questions

60,512 answers

201,930 comments

95,354 users