Counting sum of parities of cycle covers in cubic, planar, bipartite graphs

Question

Let $G$ be a cubic (i.e. every degree exactly three), planar, bipartite graph. By Hall's theorem its edges can be partitioned into three perfect matchings. Take any such partition $M_0,M_1,M_2$ and let $c_0,c_1,c_2$ be respectively the number of cycles in $M_1\cup M_2, M_2\cup M_0, M_0\cup M_1$ respectively.

Is $c_0 + c_1 + c_2 \equiv 0 \bmod{2}$? If yes, what is the proof? If not, a counterexample?

Small examples such as a cube or two concentric hexagons with $6$ cross edges etc. seem to point towards the first possibility but I am not sure either way.

Any references will be greatly appreciated!

Answer 1

Let $A, B$ be the bipartition of $G$ and $|A| = |B| = n.$

Claim: $c_1 + c_2 + c_3 \equiv n \pmod{2}.$

To show this, we can naturally associate each matching $M_i$ to a permutation $\sigma_i \in S_n.$

Define $f: S_n \to \{0, 1\}$ such that $f(\sigma) = 0$ iff $\sigma$ is an even permutation, and define $c: S_n \to \mathbb{N}$ so that $c(\sigma)$ is the number of cycles in $\sigma.$ We know that $c(\sigma) \equiv n-f(\sigma) \pmod{2}.$

Now, it is direct to see that the number of cycles in $M_i \cup M_j$ is simply $c(\sigma_j^{-1}\sigma_i) \equiv n-f(\sigma_j^{-1})-f(\sigma_i) \equiv n-f(\sigma_j)-f(\sigma_i) \pmod{2}.$ Summing gives us that $$c_1+c_2+c_3 \equiv 3n-2f(\sigma_1)-2f(\sigma_2)-2f(\sigma_3) \equiv n \pmod{2}$$ as claimed.

So you question really is: are there planar cubic graphs with an odd number of vertices on each side of the bipartition? At this point it's not hard to draw out an explicit counterexample; I'll give a sketch of how to find one.

Make 3 hexagons, so that $G$ would have $9$ vertices on both sides of its bipartition. Now, we have to add 9 more edges, 3 between each pair of hexagons that preserves the graph being bipartite and is planar. It isn't hard to just draw 9 such edges by hand. Ask if you are still having trouble, I can explicitly describe the graph then.