3
$\begingroup$

On the Wikipedia page for Wagner's theorem, we find the following description of the relation to Kuratowski's Theorem:

Wagner published both theorems in 1937, subsequent to the 1930 publication of Kuratowski's theorem, according to which a graph is planar if and only if it does not contain as a subgraph a subdivision of one of the same two forbidden graphs $K_5$ and $K_{3,3}$. In a sense, Kuratowski's theorem is weaker than Wagner's theorem: a subdivision can be converted into a minor of the same type by contracting all but one edge in each path formed by the subdivision process, but converting a minor into a subdivision of the same type is not always possible. However, in the case of the two graphs $K_5$ and $K_{3,3}$, it is straightforward to prove that a graph that has at least one of these two graphs as a minor also has at least one of them as a subdivision, so the two theorems are equivalent.

Am I crazy, or is the "In a sense, Kuratowski's theorem is weaker than Wagner's theorem" assertion completely backwards?

Of course, since both theorems are if-and-only-ifs, there are "two directions" to each theorem. But in both cases, one direction is more or less trivial: it is obvious that a planar graph cannot have a non-planar minor nor a subdivision of a non-planar graph as a subgraph.

The nontrivial direction in either case is to show that if a graph is non-planar then it must have a [$K_5$ or $K_{3,3}$ minor] / [subdivision of $K_5$ or $K_{3,3}$ as a subgraph]. Since, as the paragraph explains, any subdivision of $H$ as a subgraph can immediately be converted to an $H$ minor by contracting the "extraneous" vertices on each edge, it would seem that showing a graph has a subdivision of $K_5$ or $K_{3,3}$ as a subgraph is strictly harder than showing it has a $K_5$ or $K_{3,3}$ minor.

Is there some basic logical point I'm getting tripped up by here?

At any rate, as the quoted paragraph explains, I'm sure it's not hard to deduce one of these theorems from the other. But it would be good to correct Wikipedia on this if I am not mistaken.

EDIT: Looking at the history of the page, about a year ago the paragraph in question was edited to say "weaker" where it had said "stronger." I think this is the culprit: an erroneous edit by someone who didn't understand. I'll change it back to "stronger" now.

$\endgroup$

1 Answer 1

4
$\begingroup$

You're correct. The hard direction of both theorems is showing that any non-planar graph contains a (subdivision/minor) of $K_{3,3}$ and $K_5$. Of these, finding a subdivision is more specific, so Kuratowski's theorem (which guarantees the subdivision, and not just the minor) is more powerful.

The editor of the Wikipedia article may have been thinking of "weaker" in a non-technical sense, or by looking at the easy direction. A common task in intro graph theory classes that teach these theorems is to make students prove that a graph is not planar by finding a subdivision or minor of $K_{3,3}$ or $K_5$. Here, of course, we're using the easy direction of both theorems, and so Wagner's test is more powerful than Kuratowski's: assuming you remember the definition of a minor, finding one is easier than finding a subdivision.

$\endgroup$
1
  • $\begingroup$ Thanks for the reassurance. (Indeed, I'm teaching graph theory right now and asked this question because I wanted to make sure I got it right for my students.) Incidentally, I guess that even though Wagner's result was both later and weaker than Kuratowski's, in a way it was "more influential" in the long run because it introduced the important notion of a graph minor. $\endgroup$ Apr 19, 2020 at 17:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .