5
$\begingroup$

By Kuratowski's theorem, every nonplanar graph contains a (topological) minor of $K_5$ or $K_{3,3}$.
But I observed that every time I construct a $4$-connected nonplanar graph, it always contains not only a $K_{3,3}$-minor but also a $K_5$-minor.
Moreover, although I tried many times, I cannot construct a $4$-connected nonplanar graph containing only $K_{3,3}$-minors!
So I want to know whether the following statement is true:

Every $4$-connected nonplanar graph contains a $K_5$-minor.

Unfortunately, I could not find any references about this topic.
If the statement is true, can you give me a proof?
Or if it's not, can you show me a counterexample?
Thanks a lot.

$\endgroup$

1 Answer 1

10
$\begingroup$

Yes, this is true and follows from Wagner's theorem. Wagner's theorem asserts that every graph with no $K_5$ minor can be built from $0$-, $1$-, $2$-, and $3$-sums from planar graphs and a fixed $8$ vertex non-planar graph called the Wagner graph. Since the Wagner graph is not $4$-connected, this implies that every $4$-connected graph with no $K_5$ minor is planar.

Alternatively, there is a short proof provided you are happy to assume Kuratowski's theorem. The proof idea is to start with a model of $K_{3,3}$ and then use $4$-connectivity to 'augment' the model of $K_{3,3}$ to a model of $K_5$. See the paper A Quick Proof of Wagner's Equivalence Theorem by Young.

$\endgroup$
2
  • $\begingroup$ Thanks for nice reference! But I cannot understand his paper since it's written in Deutsch... Can you explain a brief sketch of the proof? If it is not easy, I may post another question about it. $\endgroup$
    – okw1124
    Nov 17, 2021 at 12:46
  • $\begingroup$ Thanks for editing! Now I fully understood how to prove it. $\endgroup$
    – okw1124
    Nov 19, 2021 at 4:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.