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

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!

• K_4 is a cubic nonbipartite planar graph where the assertion clearly fails — so bipartiteness is necessary. Commented Mar 11, 2019 at 19:57

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.

• sorry, I got confused by the notation while reading your answer in detail :— p is I presume the same as f? Commented Mar 13, 2019 at 15:48
• Ah, yes. I'll change that. Commented Mar 13, 2019 at 18:46