GATE 2008
March 14, 2025GATE 2008
| Question 23 |
Which of the following statements is true for every planar graph on n vertices?
| The graph is connected | |
| The graph is Eulerian
| |
| The graph has a vertex-cover of size at most 3n/4 | |
| 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 K4 graph. It has independent set size 1 which is less than 4/3.
So false.
Hence, option (C) is correct.
(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 K4 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 K4 graph. It has independent set size 1 which is less than 4/3.
So false.
Hence, option (C) is correct.
(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 K4 graph. It has independent set size 1 which is less than 4/3.
So false.
Hence, option (C) is correct.
Subscribe
Login
0 Comments