Is it true that any 3-regular bipartite graph containing $K_{3,2}$ as subgraph must be non-planar?

Question

I asked a similar question previously at Is it true that any 3-regular graph containing K_{3,2} as subgraph must be non-planar? The requirement can be relaxed so that the $K_{3,2}$ "locally" respect the bipartite structure, namely there can't be edge connecting two vertices on the dangling side. Many thanks in advance.

Answer 1

Yes, it is true.

Combinatorially speaking, there is only one plane embedding of $K_{3,2}$: the one shown below.

To complete this graph to a $3$-regular bipartite graph, there must be at least one more vertex in the component containing copy of $K_{3,2}$. That vertex must be in the interior of one of the length-$4$ faces of this plane embedding. It doesn't matter which one, but let's put it in the interior of the face with corners $v_1, w_1, v_2, w_2$.

That vertex must be part of a fragment which is bipartite and nearly $3$-regular, except for an edge to one or both of $v_1, v_2$. Crucially, since $v_1$ and $v_2$ are in the same part of the bipartition, the edges to $v_1$ and/or $v_2$ must also come from the same side of the bipartition of the fragment.

But now, suppose that the fragment has $k$ vertices in one part and $\ell$ vertices in the other part (with the edges to $v_1$ and/or $v_2$ coming from the part of size $\ell$). Then there are $3k$ edges from the first part to the second, but either $3\ell-1$ or $3\ell-2$ edges from the second part to the first. This is a contradiction, so no bipartite $3$-regular planar graph can contain a $K_{3,2}$.

---

However, if we relax the condition "bipartite" to "triangle-free", then there are many counterexamples. Take your favorite bipartite, planar, $3$-regular graph $G$; delete an edge $u_1 u_2$ on the exterior boundary of a plane embedding of $G$, and splice it into the embedding above by adding edges $u_1v_1$ and $u_2v_2$ instead. (The result is no longer bipartite, because $u_1$ and $u_2$ were in different parts of the bipartition of $G$.)

We now have a planar triangle-free graph which is $3$-regular except for $v_3$. Take two copies of this graph and join them by an edge connecting $v_3$ and its copy, and we get a planar $3$-regular triangle-free graph that contains a copy of $K_{3,2}$.