Graph G contains K₅ as a minor but does NOT contain any subdivision of K₅ or K₃,₃. By Wagner's theorem, is G planar?
AYes — G contains no subdivision of K₅ or K₃,₃, so Kuratowski's condition is satisfied and G must be planar.
BNo — Wagner's theorem shows that containing K₅ as a minor is sufficient to conclude non-planarity, and this condition is equivalent to Kuratowski's.
CWe cannot determine planarity without checking Kuratowski's condition separately from Wagner's.
DOnly K₃,₃ as a minor is relevant to planarity; K₅ minors alone do not determine it.
Wagner's theorem states that a graph is planar if and only if it contains neither K₅ nor K₃,₃ as a *minor*. The theorem proves this is equivalent to Kuratowski's subdivision condition, so no separate check is needed. The premise of the question is actually impossible — Wagner's equivalence guarantees that if G contains K₅ as a minor, it must also contain a subdivision of K₅ or K₃,₃. Option A is the classic misconception: thinking the conditions are independent.
Question 2 Multiple Choice
Why is 'containing H as a minor' a weaker condition than 'containing a subdivision of H'?
AMinors can only be formed by edge contraction, making them harder to find than subdivisions.
BA graph that contains a subdivision of H automatically contains H as a minor (by contracting the inserted degree-2 vertices), but not every minor arises from a subdivision.
CSubdivisions insert vertices that always increase the minor count of a graph.
DMinors require the graph to have more vertices, while subdivisions only require more edges.
A subdivision of H can be turned into H as a minor by contracting away the degree-2 vertices inserted along each edge. So every graph containing a subdivision of H also contains H as a minor — meaning 'contains H as minor' is satisfied by a larger class of graphs. For general H, this gap is real: graphs can contain H as a minor without any subdivision. The surprise of Wagner's theorem is that for K₅ and K₃,₃ specifically, the gap closes and the two conditions are equivalent.
Question 3 True / False
Wagner's theorem and Kuratowski's theorem give equivalent characterizations of planarity, even though graph minors and subdivisions are different structural relationships.
TTrue
FFalse
Answer: True
This is Wagner's theorem. Despite 'containing H as a minor' being a weaker (more permissive) condition than 'containing a subdivision of H,' both conditions identify exactly the same set of non-planar graphs when H ranges over {K₅, K₃,₃}. The proof shows that any graph with K₅ or K₃,₃ as a minor also contains a subdivision of one of them, closing the gap for these two specific graphs.
Question 4 True / False
Since 'containing H as a minor' is weaker than 'containing a subdivision of H,' Wagner's theorem forbids a strictly larger class of graphs than Kuratowski's theorem.
TTrue
FFalse
Answer: False
The two conditions are equivalent — they forbid exactly the same class of graphs. Although the minor relation is logically weaker in general, Wagner's theorem proves that for K₅ and K₃,₃, any graph containing one of them as a minor also contains a subdivision of one of them. So no graph is banned by Wagner that isn't also banned by Kuratowski, and vice versa. The planarity boundary is the same; only the characterization language differs.
Question 5 Short Answer
Why does Wagner's theorem matter beyond being an alternative restatement of Kuratowski's theorem?
Think about your answer, then reveal below.
Model answer: Wagner's theorem frames planarity using graph minors, which opens the door to the Robertson–Seymour Graph Minor Theorem: every minor-closed family of graphs can be characterized by a finite list of forbidden minors. Planar graphs form a minor-closed family (any minor of a planar graph is planar), and Wagner identifies its two forbidden minors as K₅ and K₃,₃. This turns planarity into the prototype for a vast classification program — the same question ('what are the forbidden minors?') can be asked for graphs on other surfaces, graphs of bounded treewidth, and many other families.
The shift from subdivisions to minors is not just notational. Minors define a partial order on graphs (the graph minor order), and the Robertson–Seymour theorem proves this order is a well-quasi-order — implying every minor-closed family has finitely many forbidden minors. Wagner's theorem is the first and most elegant instance of this general theory.