8,085 views

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

moved by
Answer is (A) The graph is connected
Yeah it should be C. I came to the same conclusion, following the same reasoning
Planar graph dont need to be connected.
This is not out of syllabus.
not out of syllabus. 2016 question came from here

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.

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

exactly correct explaination

Is it out of syllabus now?

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$

### Subscribe to GO Classes for GATE CSE 2022

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.

by

I can't find any source for the formula for independent set$\geq \left \lceil n/k \right \rceil$. Please cite your source.
@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$
I didn't get your sentence. Can't every planar be colored with at most $4$ color only? why it is at least 3 or 4?

@Mk Utkarsh did you edit 1st line in the answer , if yes did you change 2 in place of k

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 :

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.

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.

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.

by

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

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

by

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 )

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

1
4,400 views
2
3
13,400 views