Which one of the following graphs is NOT planar? A. G1 B. G2 C. G3 D. G4

GATE 2005 · Discrete Mathematics · Graph Planarity · medium

Answer: G1 is NOT planar.

1. Apply the planar edge bound to each graph: For each of G1-G4, count vertices and edges. G1 (based on the figure: a pentagonal structure with internal cross-edges akin to K5) has |V| = 5 and |E| = 10, which violates 10 <= 3*5-6 = 9.
2. Confirm G1 is non-planar by Kuratowski's theorem: G1's structure contains a subdivision of K5 (a complete graph on 5 vertices). The remaining graphs G2, G3, G4 are planar since they can be embedded in the plane without crossings.