GATE CS 2007 Q4 — Graphs: Connectivity, Matching, Colouring

According to Kuratowski's Theorem, a graph is non-planar if and only if it contains a subgraph that is a subdivision of $K_5$ (the complete graph on 5 vertices) or $K_{3,3}$ (the complete bipartite utility graph on $3+3$ vertices).

A subdivision of a graph $H$ is obtained by inserting vertices of degree 2 into its edges. This operation can only increase or keep the number of edges the same. Thus, any non-planar graph must have at least as many edges as either $K_5$ or $K_{3,3}$.

Let's analyze the number of vertices ($V$) and edges ($E$) for these two base non-planar graphs:

• For $K_5$: $$V = 5, \quad E = \binom{5}{2} = 10$$
• For $K_{3,3}$: $$V = 6, \quad E = 3 \times 3 = 9$$

The minimum number of edges required for a graph to be non-planar is therefore $\min(10, 9) = 9$. This minimum is achieved by $K_{3,3}$, which has 9 edges and 6 vertices.

Why is a graph with 9 edges and 5 vertices planar?
Any simple graph with $V = 5$ and $E = 9$ is planar. Since it has only 5 vertices, it cannot contain a subdivision of $K_{3,3}$ (which requires at least 6 vertices). It also cannot contain $K_5$ because $K_5$ requires 10 edges. By Kuratowski's Theorem, such a graph must be planar.

Thus, the non-planar graph with the minimum possible number of edges has 9 edges and 6 vertices.