Question 10586 – GATE 1989

(i) G₁ is K₃₃ which is planar graph with the minimum number of edges.
→ Let us assume K₃₃is a planar graph. Then it satisfy the useful corollary. As there is no triangle in K₃₃.
Let G be a connected planar graph with n vertices and m edges, and no triangles. Then m≤2n-4.
Where m=9, n=6
⇒ 9 ≤ 12 – 4
⇒ 9 ≤ 8, which is to be false, then K₃₃ is non-planar graph.
(ii) G₂ is a planar graph. Because it can be redrawn like as below.

(iii) Let us assume G₃ be a planar graph then it also be satisfy useful corollary.
Where m=9, n=6
then 9 ≤ 12-4
9 ≤ 8 is False
So, G₃ is non-planar graph.
Answer: Only G₂ is planar graph.