A non-planar graph with minimum number of vertices has A. 9 edges, 6 vertices B. 6 edges, 4 vertices C. 10 edges, 5 vertices D. 9 edges, 5 vertices

GATE 1992 · Discrete Mathematics · Graph Planarity · medium

Answer: 5 vertices and 10 edges (K_5) -> Option C.

1. Smallest non-planar graph by vertices: Every graph on <= 4 vertices is planar, so non-planarity first appears at 5 vertices with K_5; K_{3,3} needs 6 vertices. The minimum is K_5.
2. Count edges of K_5: C(5,2) = 5 x 4 / 2 = 10 edges. (Dropping any edge makes K_5 minus e planar, so the 9-edge option D is planar.)