The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+12 votes
1.7k 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}$
asked in Graph Theory by Veteran (59.5k points)
edited by | 1.7k views
–2
Answer is (A) The graph is connected
0
Yeah it should be C. I came to the same conclusion, following the same reasoning
0
Planar graph dont need to be connected.
0
This is not out of syllabus.
+2
not out of syllabus. 2016 question came from here
0

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.

3 Answers

+13 votes
Best answer

Independent Set $\geq$ ceil$(n/k)$ 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.

answered by (313 points)
edited by
0
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$
+10 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.

answered by Loyal (5.7k points)
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
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
+1 vote

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.

answered by (185 points)


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

39,713 questions
46,750 answers
140,552 comments
58,384 users