Cubic planar bipartite graphs are dispersable ^††thanks: As submitted for publication on 7/20/2020; see Postscript for additional information.

The oriented degree $\deg(v)$ of a vertex in a digraph is the number of edges in minus the number of edges out. The sum of all oriented vertex degrees for any digraph is zero.

Let $(H$, $u^{\prime}$, $u^{\prime\prime})$ be as in the statement; give $G$ and $H$ the edge-orientation induced from the bipartition by orienting the edges from white to black, so each vertex has oriented degree $\pm k$ according to whether it’s black or white. Put

We have

For each $v\in W$, $\deg_{H}(v)=\deg_{G}(v)$, so $\sum_{v\in W}\deg_{H}(v)\cong 0$ (mod $k$), hence, by (1), $\deg_{H}(u^{\prime})+\deg_{H}(u^{\prime\prime})\cong 0$. As $k\geq 3$, $2k-2\ncong 0$ (mod $k$), so the degrees of $u^{\prime}$ and $u^{\prime\prime}$ must be of opposite sign, i.e., $u^{\prime}$ and $u^{\prime\prime}$ are in different parts. ∎

Let $G$ be a connected $k$-regular bipartite graph. If $k=0$ or $1$, then $G$ is $K_{1}$ or $K_{2}$, resp., and there are no cutpoints. For $k=2$, bipartite or not, $G$ is a cycle and so has no cutpoint or bridge. Suppose now $k\geq 3$. Let $u$ be a cutpoint of $G$ and let $\Gamma$ be a connected component of $G-u$.

We define $J:=\Gamma+u:=G(V(\Gamma)\cup\{u\})$ to be the smallest subgraph of $G$ containing $\Gamma$ and $u$. Then again using oriented degrees,

the second summand is congruent to zero (mod $k$) but $\deg_{J}(u)\ncong 0$ (mod $k$) so no cutpoint $u$ can exist. ∎

If $G$ is cubic and $f_{1},f_{2}$ are parallel edges joining vertices $a$ and $b$, then either (i) there is a third parallel edge $f_{3}$ and $G$ contains the trivial cubic graph as a connected component or (ii) the remaining two edges $f_{3}$ and $f_{4}$ at $a$ and $b$, resp., are a cutset for $G$, as they separate $\{a,b\}$ from the other vertices. ∎

Let $G$ be a bipartite cubic planar multigraph. Assume without loss of generality ([3], [16]) that $G$ is connected. We need to show that $G$ has a subhamiltonian vertex order $\omega$ and an edge-3-coloring $c$ such that in the outerplane drawing $(G,\omega)$, each color class of $c$ is crossing-free; that is,

Suppose that $G$ is a counterexample with the minimum number of vertices. Note that $G$ must be a nontrivial cubic multigraph as the required $\omega$ and $c$ do exist for $\Theta$, and $G$ cannot be $3$-connected else it is dispersable by Theorem 1 which applies as there can be no parallel edges.

Since $G$ is bipartite and cubic, by Proposition 1 it has no cutpoint and hence must be 2-connected. As line-connectivity and point-connectivity coincide for cubic graphs [9, p. 55, ex. 5.6 ], there must be a cutset of two edges. But the two edges of such a cutset cannot share a vertex – the third edge at a common vertex would be a bridge. Hence, $G$ contains vertex-disjoint edges $e^{\prime}=u^{\prime}w^{\prime},\;e^{\prime\prime}=u^{\prime\prime}w^{\prime\prime}$ (neither of which is a parallel edge) such that

where $G_{1}$ and $G_{2}$ are vertex-disjoint. Further, by Lemma 1, $u^{\prime}$ and $u^{\prime\prime}$ are in distinct parts of the bipartition of $G_{1}$ induced by the bipartition of $G$, and similarly for $w^{\prime},w^{\prime\prime}$ in the corresponding bipartition of $G_{2}$.

Let $H_{1}=G_{1}+e_{1}$, where $e_{1}:=u^{\prime}u^{\prime\prime}$, $H_{2}=G_{2}+e_{2}$, where $e_{2}:=w^{\prime}w^{\prime\prime}$. Then $H_{1}$ and $H_{2}$ are bipartite cubic planar multigraphs, either of which can contain multiple edges even if $G$ has no parallel edges. As $|H_{1}|,|H_{2}|<|G|$, there exist cyclic orderings $\omega_{1},\omega_{2}$ on $V(H_{1})=V(G_{1})$ and $V(H_{2})=V(G_{2})$, resp., and edge colorings $c_{1},c_{2}$ which constitute dispersable subhamiltonian book embeddings of $H_{1}$ and $H_{2}$. Let $\lambda_{1}$ be one of the two possible linear orderings obtained from $\omega_{1}$ which starts at $u^{\prime\prime}$. Similarly, let $\lambda_{2}$ be one of the two possible linear orderings obtained from $\omega_{2}$ which starts at $w^{\prime\prime}$.

Define $\lambda$ a linear order on $V(G)=V(H_{1})\cup V(H_{2})$ by the equation $\lambda:=\lambda_{1}^{op}\,*\,\lambda_{2}$, where $\lambda_{1}^{op}$ is the opposite (i.e., reverse) order to $\lambda_{1}$ and $*$ denotes concatenation. Let $\omega$ be the cyclic order determined by $\lambda$. Observe that $u^{\prime\prime}$ and $w^{\prime\prime}$ are consecutive in the subhamiltonian ordering of $V(G)$ given by $\omega$.

By renaming the colors, we can assume that the colorings $c_{1}$ and $c_{2}$ both use colors $\{\alpha,\beta,\gamma\}$ and that $e_{1}$ and $e_{2}$ are both assigned $\gamma$. Define $c$ an edge 3-coloring of $E(G)$ to be $c_{1}$ on $E(G_{1})$, $c_{2}$ on $E(G_{2})$, and put $c(e^{\prime})=c(e^{\prime\prime})=\gamma$. If $e\in E(G_{1})$ is adjacent to either $e^{\prime}$ or $e^{\prime\prime}$, then $e$ was adjacent to $e_{1}$, so $c(e)\neq c(e^{\prime})$ and similarly for $G_{2}$. Observe that $e^{\prime\prime}$ has no crossings in $(G,\omega)$.

Figure 2   Subhamiltonian dispersable embedding of $G$

We claim $e^{\prime}$ crosses no edge colored $\gamma$. For if $e=xy$ crosses $e^{\prime}$ in the drawing $(G,\omega)$, then $x$ and $y$ both belong to $G_{1}$ or both belong to $G_{2}$; else $\{e^{\prime},e^{\prime\prime}\}$ wouldn’t be a cutset. Thus $xy$ must cross $e_{1}$ or $e_{2}$, hence $c(xy)\neq\gamma$. So $(\omega,c)$ is a dispersable subhamiltonian book embedding of $G$ which is impossible. ∎