Which one of the following graphs is NOT planar?

Answer: G1 is not planar.

Key idea: A graph is nonplanar if it contains a subdivision of K5 or K3,3 (Kuratowski's theorem).

Reason G1 is nonplanar:

• G1 is isomorphic to the complete bipartite graph with partitions of size 3 (K3,3).

• K3,3 is nonplanar by Kuratowski's theorem, so any graph containing it (or a subdivision of it) is nonplanar.

• Alternative quick check: For triangle-free planar graphs the inequality e ≤ 2v − 4 holds. G1 has v = 6 and e = 9, but 9 > 2·6 − 4 = 8, so G1 cannot be planar.

Why the others are planar (brief):

• G2: does not contain K5 or K3,3 subdivisions and can be drawn without crossings (a plane embedding exists).

• G3: outerplanar (all vertices can be placed on a circle and edges drawn inside without crossings), so it is planar.

• G4: although relatively dense, it contains no subdivision of K5 or K3,3 and admits a plane embedding.

Conclusion: G1 is the only nonplanar graph among the choices because it contains K3,3 (or fails the triangle-free planar edge bound).