Questions: Planar Graphs: Kuratowski's and Wagner's Theorems

Question 1

A graph G has 10 vertices, 20 edges, and 12 faces. Since V − E + F = 10 − 20 + 12 = 2, Euler's formula is satisfied. Can you conclude that G is planar?

• A. Yes — Euler's formula is satisfied, confirming G is planar
• B. No — Euler's formula is a necessary condition for planarity but not sufficient; you would need to verify G contains no subdivision of K₅ or K₃,₃
• C. Yes — if V − E + F = 2 holds, the graph must be embeddable in the plane
• D. It depends on whether G is connected and simple

Answer: (B)

Euler's formula provides a necessary condition: any connected planar graph must satisfy V − E + F = 2. But satisfying the formula doesn't prove planarity — the formula can't even be evaluated without first assuming a planar embedding exists. Kuratowski's theorem gives the complete if-and-only-if characterization: G is planar exactly when it contains no subdivision of K₅ or K₃,₃.

Question 2

Graph G contains K₃,₃ as a minor (obtained by contracting and deleting edges). What does Wagner's theorem tell you about G?

• A. G is non-planar only if it also contains K₃,₃ as a subdivision
• B. G is non-planar — having K₃,₃ as a minor is sufficient by Wagner's theorem
• C. Wagner's theorem applies only to K₅, not K₃,₃
• D. G might still be planar since K₃,₃ appears only as a minor, not as a subgraph

Answer: (B)

Wagner's theorem states: a graph is planar if and only if it contains no minor isomorphic to K₅ or K₃,₃. Having K₃,₃ as a minor is sufficient to conclude non-planarity — this is the full biconditional. Options A and D reflect a common confusion: minors are a coarser relation than subdivisions, but both are sufficient to certify non-planarity.

Question 3

Kuratowski's theorem proves that nearly every non-planar graph IS either K₅ or K₃,₃.

• T. True
• F. False

Answer: False

Kuratowski's theorem says a graph is non-planar if and only if it CONTAINS a subdivision of K₅ or K₃,₃ — not that it equals one. Non-planar graphs can be arbitrarily large and complex; what's guaranteed is that somewhere inside them you can find a K₅ or K₃,₃ subdivision as a pattern. The theorem characterizes non-planarity by a forbidden pattern, not by identity with those two graphs.

Question 4

If a graph G contains a subdivision of K₅, then G also contains K₅ as a minor.

• T. True
• F. False

Answer: True

Every subdivision is a minor. A subdivision of K₅ inserts degree-2 vertices along edges; contracting those inserted vertices back down gives K₅ itself, which is therefore a minor of G. This is why minors are a coarser relation: every subdivision is a minor, but not every minor arises from subdivision. Wagner's theorem uses the coarser condition (minors) while Kuratowski's uses the finer one (subdivisions), yet both equivalently characterize planarity.

Question 5

Explain the difference between a subdivision and a minor of a graph. Which operation is coarser, and why are both sufficient to detect non-planarity?

Model answer: A subdivision inserts new degree-2 vertices along edges, replacing each edge with a path. A minor is obtained by contracting edges (merging their endpoints) and deleting edges or vertices — a strictly more permissive operation. Minors are coarser. Every subdivision is a minor (contract the inserted vertices back), but not every minor arises from subdivision. Both detect non-planarity because neither operation can make a non-planar graph planar: if G can be drawn without crossings, any graph obtained by subdividing or contracting its edges can also be drawn without crossings.

The equivalence of Kuratowski's and Wagner's characterizations shows that non-planarity is robust under both operations. This robustness is the seed of the Robertson-Seymour theorem, which generalizes Wagner's result to prove that any minor-closed graph property has a finite forbidden minor characterization — one of the deepest results in graph theory.