October 24, 2023
October 24, 2023
October 24, 2023
GATE 2007
October 24, 2023
 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
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.
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.