6
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
11
$\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.

Improve this answer
$\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
    Commented Nov 17, 2021 at 12:46
  • $\begingroup$ Thanks for editing! Now I fully understood how to prove it. $\endgroup$
    – okw1124
    Commented Nov 19, 2021 at 4:45

You must log in to answer this question.

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