in Graph Theory edited by
8,085 views
32 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}$
in Graph Theory edited by
8.1k views

11 Comments

moved by
Answer is (A) The graph is connected
–2
Yeah it should be C. I came to the same conclusion, following the same reasoning
0
Planar graph dont need to be connected.
3
This is not out of syllabus.
0
not out of syllabus. 2016 question came from here
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.

6

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

20

 exactly correct explaination

0
Is it out of syllabus now?
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$

0

Subscribe to GO Classes for GATE CSE 2022

6 Answers

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

6 Comments

I can't find any source for the formula for independent set$\geq \left \lceil n/k \right \rceil$. Please cite your source.
2
@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$
12
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?
1

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

0

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 :  

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

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 K4 . Now only one option (C)  left  .

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

by

6 Comments

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
0
We can prove C using every planar graph is 4 colourable.
0
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?
0
you can also take any example of wheel graph with vertices greater 6 u should take 6

all have independence set 1
0
1 vote

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

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 )

0 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}$.
Answer:

Related questions

Ask
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true