I was trying to prove this exercise from Diestel's book:

Show that adding a new edge to a maximal planar graph of order at least 6 always produces both a $TK_5$ and a $TK_{3,3}$ subgraph.

I used a hint from Diestel's book to get a topological minor of $K_5$, but I had trouble finding the $TK_{3,3}$. I found a solution here (The $K_5$-part is the same thing I did).

However, I don't understand a part of it when they try to find the $TK_{3,3}$ subgraph. They say:

Since $G$ has order at least $6$, there is another vertex $z$ distinct from those previously mentioned. The construction allows for two cases: either $z$ lies outside the region bounded by the topological cycle $vu_1wu_2v$ or it lies inside one of the faces of this region (they are all equivalent).

My question is why cannot $z$ be in the boundary of $vu_1wu_2v$? And it that were possible, the three disjoint paths from $z$ to $u_1,u_2,u_3$ might not be disjoint to the previous drawn paths, which seems to cause trouble when building the $K_{3,3}$-subdivision.


I think that solution is wrong already at the following point.

Since $v$ is not adjacent to $w$ (else we could add no edge between them), we can find vertices $u_1$, $u_2$, and $u_3$ lying one on each path that are neighbors of $v$ but not of $w$.

If a path from $v$ to $w$ has length $2$ then a neighbor $u$ of $v$ at the path is a neighbor of $w$.

By the edge-maximality of $G$, $u_1$, $u_2$, and $u_3$ induce a cycle.

This is true, if $v$ has degree three. Otherwise it may fail (for instance, see the picture).

enter image description here

  • $\begingroup$ You're right. Fortunately, I had modified that part to just take the three paths in such a way each of them only contained one neighbor of $v$. About the use of the edge maximality of $G$, I think that to produce the subdivision of $K_5$ we only need to make sure all the neighbors of $v$ form a cycle. $\endgroup$ – Nell Dec 28 '18 at 3:27

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.