The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+11 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}$
asked in Graph Theory by Veteran (59.5k points)
edited by | 1.6k views
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

2 Answers

+12 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 (303 points)
edited 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$
+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.6k points)
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

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

37,117 questions
44,701 answers
43,763 users