I'm working on the following problem.
Show that adding a new edge to a maximal planar graph
of order at least 6 always produces subdivisions of both $K_5$ of $K_{3,3}$.
I had no trouble getting the subdivision of $K_5$ (I had to modify my attempt a bit based in the sketch of a solution I found here, since there were some cases I hadn't covered).
But I have trouble getting the subdivision of $K_{3,3}$.
So, with the notation from the link, I am here:
Let $G$ be maximal planar, $v_1,v_2$ two vertices; we want to build some edge between them and see this ends up with a graph having a subdivision of $K_{3,3}$.
We also have three $u-v$ vertex disjoint paths, say, $P_1,P_2,P_3$, each of them only having one neighbor of $v$, say, $u_1,u_2,u_3$. We also have that the neighbors of $v$ form a cycle since $G$ is a triangulation of the plane.
Also as they say, we have a new vertex $w$, which we may suppose is (given, if necessary, a rotation of the sphere which interchanges some faces) inside one of the regions bounded by the cycles determined by $P_i$ and $P_j$, say, $P_1$ and $P_2$. In this case, by Menger's theorem we have three paths to $u_1,u_2$ and $v_2$.
Anyways, we have the following sketch of the situation:
The curly 'edges' mean they are paths, the red dashed edge means it's the edge we want to add. In the solution they say that with this we get a subdivision of $K_{3,3}$ with partition given by $A=\{u,w,u_3\}$ and $B=\{u_1,u_2,v\}$. In the picture suppose the $u_1-u_2,u_2-u_3,u_3-u_1-$ paths are $\zeta_1,\zeta_2,\zeta_3$. If the three paths from $w$ don't meet $\zeta_2$ or $\zeta_3$ we don't have much trouble and that's indeed a partition of those six vert which, with the edges and paths we already have and $v_1v_2$ make a subdivision of $K_{3,3}$. But if the paths from $w$ somehow meet $\zeta_2$ or $\zeta_3$ we may need to change the vertices which make the subdivision.
So, are those both cases possible? If they are, is there some way to handle them?
Edit: There is also this question but they only talk about how some solution (a bit different from mine) is wrong.
Best Answer
I know it has a bit of irony that I found a way to solve it just after putting the bounty. I had proven before that every $3-$connected nonplanar graph contains a $K_{3,3}-$minor, but hadn't really realized that it also has a $K_{3,3}-$subdivision (In my proof there was a part when I couldn't find such subdivision but I still was able to get a minor so since that's what I wanted to find I didn't worry about that; now, after verifying that part, I see that such subdivision can be easily found given what I already had).
So, I can use the proof of the lemma 3.4 here.
In this case I can find a subdivision of $K_{3,3}$ in any $3-$connected nonplanar graph, in particular one built by adding an edge to a maximal planar graph.