GATE 2007

Question 4

Let G be the non-planar graph with the minimum possible number of edges. Then G has

A	9 edges and 5 vertices
B	9 edges and 6 vertices
C	10 edges and 5 vertices
D	10 edges and 6 vertices

Engineering-MathematicsGraph-Theory

Question 4 Explanation:

Using Euler’s formula we know that,
if n ≥ 3 then e ≤ 3n-6 (for planarity)
where n = no. of vertices
e = no. of edges
Now lets check the options.
A) e=9, n=5
9 ≤ 3(5) – 6
9 ≤ 15 – 6
9 ≤ 9

Yes, it is planar.
B) e=9, n=6
9 ≤ 3(6) – 6
9 ≤ 18 – 6
9 ≤ 12
Yes, it is planar.
iii) e=10, n=5
10 ≤ 3(5) – 6
10 ≤ 15 – 6
10 ≤ 9
No, it is not planar.
So, option C is non-planar graph.

iv) e=10, n=6
10 ≤ 3(6) – 6
10 ≤ 18 – 6
10 ≤ 12
Yes, it is planar.

Correct Answer: C

Question 4 Explanation:

Using Euler’s formula we know that,
if n ≥ 3 then e ≤ 3n-6 (for planarity)
where n = no. of vertices
e = no. of edges
Now lets check the options.
A) e=9, n=5
9 ≤ 3(5) – 6
9 ≤ 15 – 6
9 ≤ 9

Yes, it is planar.
B) e=9, n=6
9 ≤ 3(6) – 6
9 ≤ 18 – 6
9 ≤ 12
Yes, it is planar.
iii) e=10, n=5
10 ≤ 3(5) – 6
10 ≤ 15 – 6
10 ≤ 9
No, it is not planar.
So, option C is non-planar graph.

iv) e=10, n=6
10 ≤ 3(6) – 6
10 ≤ 18 – 6
10 ≤ 12
Yes, it is planar.

DSSSB TGT 2017

GATE 2007

DSSSB TGT 2017

GATE 2007

GATE 2007