question archive Wagner's Theorem states that a graph G is planar if and only if G does not contain K5 or K3,3 as a minor
Wagner's Theorem states that a graph G is planar if and only if G does not contain K5 or K3,3 as a minor
Subject:MathPrice: Bought3
Wagner's Theorem states that a graph G is planar if and only if G does not contain K5 or K3,3 as a minor.
(a) Show that deletion and contraction of edges preserves planarity. Conclude from this that the condition "G does not contain K5 or K3,3 as a minor" is necessary.
(b) Use Kuratowski's Theorem to prove that this condition is also sufficient.
