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!

  • $\begingroup$ K_4 is a cubic nonbipartite planar graph where the assertion clearly fails — so bipartiteness is necessary. $\endgroup$
    – SamiD
    Mar 11 '19 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.

  • $\begingroup$ sorry, I got confused by the notation while reading your answer in detail :— p is I presume the same as f? $\endgroup$
    – SamiD
    Mar 13 '19 at 15:48
  • $\begingroup$ Ah, yes. I'll change that. $\endgroup$
    – yangpliu
    Mar 13 '19 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.