Adding an edge to a maximal planar graph results in topological minors of both $K_5,K_{3,3}$.

Question

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.

Answer 1

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).

Answer 2

We can find a $TK_{3,3}$ in $G+e$ as follows ($e$ is the newly added edge that makes $G$ non-planar).

Let a $TK_5$ in $G+e$ be given. If $TK_5 = K_5$, then there is a vertex $w \notin K_5$ and paths $P_1,P_2,P_3$ from $w$ to $K_5$, which are disjoint up to $w$. These $P_i$ with the $K_5$ contain a $TK_{3,3}$.

Suppose now that the $TK_5$ contains a subdividing vertex $w$, which lies in an 'edge' $Q_1$ of the $TK_5$ (so $Q_1$ is one of the $10$ 'edges'), and let $q_{1,start},q_{1,end}$ be its end vertices. Since $G+e$ is still $3$-connected, then after removing $q_{1,start},q_{1,end}$, we can still make a path $P$ from $w$ to $TK_5\setminus Q_1$. Let $a$ be the last vertex of $P$ in $Q_1$, and let $b$ be the first vertex of $P$ in $TK_5\setminus Q_1$. Say $b$ lies in another 'edge' $Q_2$, and let $q_{2,start},q_{2,end}$ be its end vertices. If $b$ is a branch vertex, then $TK_5 \cup aPb$ contains a $TK_{3,3}$. If $b$ is a subdividing vertex, then wlog let $q_{2,start}$ be a branch vertex which is not in $\lbrace q_{1,start},q_{1,end}\rbrace$. Now $TK_5/bQ_2q_{2,start} \cup aPb$ contains a $TK_{3,3}$. A $TK_{3,3}$ is also a $IK_{3,3}$ by Prop. 1.7.3 (i) of Diestel 2017. Hence $G+e$ contains an $IK_{3,3}$ by Cor. 1.7.2. By Prop. 1.7.3 (ii) we are done.