These theorems stated by Wikipedia seems very similar; difficult to decipher the difference. Can someone elaborate?
$\endgroup$1 Answer
$\begingroup$Kuratowski's theorem is about subgraphs; Wagner's theorem is about minors. Every subgraph is a minor, but not vice versa: to get a minor you are allowed to merge vertices along a common edge, but to get a subgraph you are only allowed to delete edges (and vertices).
A good example of this is given by the Petersen graph:
It has $K_5$ as a minor: in the standard pentagram picture you can see above, you can contract the edges connecting the inner and outer vertices to get a $K_5$. However, it does not have any subdivision of $K_5$ as a subgraph (this would require that it have vertices of degree 4).
So you can combine one direction of Wagner's theorem and the other direction of Kuratowski's theorem to conclude that the Petersen graph must contain a subdivision of $K_{3,3}$, even though this is not immediately obvious. (If you're curious, you can see such a subdivision here.)
$\endgroup$ 8
