Which of the following graphs is/are planar? G1: a graph on 6 vertices drawn as three rows of two vertices each with the complete bipartite K_{3,3} crossing pattern. G2: the 3-cube (Q3) drawn as one square inside another with corresponding corners joined. G3: a 6-vertex graph drawn with a top apex, two upper-side vertices, two lower-side vertices and a bottom apex, with the diagonals meeting near the centre.

GATE 1989 · Discrete Mathematics · Graph Planarity · medium

Answer: G2 and G3 are planar; G1 = K_{3,3} is not planar.

1. G1 is K_{3,3}: G1's three top vertices are each joined to all three bottom vertices: that is K_{3,3} itself, a forbidden Kuratowski graph, so G1 is NOT planar.
2. G2 (cube) and G3 redraw planar: The 3-cube Q3 redraws as a square inside a square (its Schlegel diagram) with no crossings, and G3's single central crossing can be undone by moving one edge outside, so both are planar.