GATE 2008

Question 23

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

A	The graph is connected
B	The graph is Eulerian
C	The graph has a vertex-cover of size at most 3n/4
D	The graph has an independent set of size at least n/3

Question 23 Explanation:

Lets do with elimination method,
(A) Consider the following disconnected graph which is planar.

So false.
(B) A graph is Eulerian if all vertices have even degree but a planar graph can have vertices with odd degree.

So false.
(D) Consider K₄ graph. It has independent set size 1 which is less than 4/3.

So false.
Hence, option (C) is correct.

Correct Answer: C

Question 23 Explanation:

Lets do with elimination method,
(A) Consider the following disconnected graph which is planar.

So false.
(B) A graph is Eulerian if all vertices have even degree but a planar graph can have vertices with odd degree.

So false.
(D) Consider K₄ graph. It has independent set size 1 which is less than 4/3.

So false.
Hence, option (C) is correct.