GATE CS 2005 Q47 — Graphs: Connectivity, Matching, Colouring

To determine which graph is NOT planar, we can use the properties of planar graphs and Kuratowski's Theorem.

Analysis of $G_1$:

• Count the number of vertices ($n$) and edges ($e$) in $G_1$:
  • $G_1$ has $n = 5$ vertices.
  • Each vertex is connected to every other vertex, making it the complete graph $K_5$. Thus, the number of edges is: $$e = \frac{5 \times 4}{2} = 10$$
• For any simple, connected planar graph with $n \ge 3$ vertices, the maximum number of edges is bounded by: $$e \le 3n - 6$$
• Substituting $n = 5$ into the formula: $$e \le 3(5) - 6 = 9$$
• Since $G_1$ has $10$ edges, and $10 > 9$, it violates this necessary condition for planarity.

By Kuratowski's Theorem, any graph containing a subgraph homeomorphic to $K_5$ or $K_{3,3}$ is non-planar. Since $G_1$ is exactly $K_5$, it is not planar.

The other graphs $G_2$, $G_3$, and $G_4$ can all be redrawn on a plane without any edge crossings, making them planar.

Therefore, the correct option is A.