Questions: Kuratowski's Theorem and Forbidden Minors

Question 1

A student examines graph G and finds a subgraph that is a subdivision of K₅. What can the student immediately conclude?

• A. G might or might not be planar — a K₅ subdivision is necessary but not sufficient for non-planarity
• B. G is non-planar, by Kuratowski's theorem
• C. G is planar, since the K₅ subdivision has been identified and can be isolated from the rest of the graph
• D. G is non-planar only if it also contains a K₃,₃ subdivision

Answer: (B)

Kuratowski's theorem says a graph is planar if and only if it contains NO subdivision of K₅ or K₃,₃. Finding a K₅ subdivision in G confirms G is non-planar — you only need one forbidden subdivision. Options A and D misread the theorem: you don't need both, and the condition is 'if and only if,' so a subdivision is both necessary and sufficient (in the negative direction). Option C is incorrect because the crossing structure of the subdivision cannot be isolated away from the rest of the graph.

Question 2

Why are K₅ and K₃,₃ specifically the two forbidden subgraphs in Kuratowski's theorem, rather than some other pair of graphs?

• A. They are the minimal non-planar graphs: removing any single edge or vertex from either one yields a planar graph
• B. They were chosen arbitrarily to provide a simple two-element characterization
• C. They are the two densest graphs that can be drawn in the plane with crossings
• D. They are the only graphs whose vertex count exceeds the planar Euler bound E ≤ 3V − 6

Answer: (A)

K₅ and K₃,₃ are the unique minimal non-planar graphs. Every proper subgraph of each is planar (remove any vertex or edge and the result can be drawn without crossings). This minimality is what makes them the correct 'obstructions': any non-planar graph must contain a subdivision of one of them, but no smaller non-planar structure exists. Option D is partially true but incomplete — K₃,₃ is bipartite (no triangles), so the relevant bound is E ≤ 2V − 4, and many other graphs also violate Euler bounds without being minimal.

Question 3

According to Kuratowski's theorem, a graph is planar if and only if it contains no subgraph that is a subdivision of K₅ or K₃,₃.

• T. True
• F. False

Answer: True

This is the exact statement of Kuratowski's theorem (1930). It is a biconditional: planar graphs have no such subdivision (⇒ direction), and any graph without such a subdivision is planar (⇐ direction, the harder direction proved by Kuratowski). The 'if and only if' is crucial — it means the two forbidden subdivisions completely characterize the boundary between planar and non-planar graphs.

Question 4

Inserting a new degree-2 vertex into the middle of an edge of a non-planar graph can make the graph planar.

• T. True
• F. False

Answer: False

A subdivision of a graph — obtained by inserting degree-2 vertices along edges — preserves planarity status in both directions. If G is non-planar and contains a K₅ (or K₃,₃) subdivision, subdividing more edges of G still leaves that forbidden subdivision present as a subgraph. Conversely, if G is planar, any subdivision of G is also planar. Topology only cares about which vertices are connected and how paths route between them, not about intermediate degree-2 vertices on edges.

Question 5

What is a 'subdivision' of K₅, and why is the concept of subdivision (rather than subgraph isomorphism to K₅ itself) the right tool for characterizing planarity obstructions?

Model answer: A subdivision of K₅ is obtained by replacing each edge of K₅ with a path of one or more edges (inserting any number of degree-2 vertices along edges). The result has the same 5 'branch' vertices of degree 4, but the edges between them may pass through additional intermediate vertices. Subdivision is the right concept because planarity depends on the crossing structure of connections between high-degree vertices, not on the exact length of paths between them. A degree-2 vertex in the middle of a path cannot resolve a crossing, so the obstruction is preserved regardless of how many intermediate vertices are added.

This is why the theorem uses 'subdivision' rather than 'K₅ as a subgraph' — a graph can contain K₅-like crossing structure without having 5 vertices of degree 4 adjacent to each other. Any graph with a topological copy of K₅ (the connectivity is there, paths may be stretched) inherits K₅'s non-planarity. The related Wagner's theorem restates this using 'minors' (edge contractions instead of subdivisions), giving an equivalent but differently expressed characterization.