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

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). • 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. – Nell Dec 28 '18 at 3:27