<p>Let <span class="math-container">$A, B$</span> be the bipartition of <span class="math-container">$G$</span> and <span class="math-container">$|A| = |B| = n.$</span></p>

<p><strong>Claim:</strong> <span class="math-container">$c_1 + c_2 + c_3 \equiv n \pmod{2}.$</span></p>

<p>To show this, we can naturally associate each matching <span class="math-container">$M_i$</span> to a permutation <span class="math-container">$\sigma_i \in S_n.$</span></p>

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

<p>Now, it is direct to see that the number of cycles in <span class="math-container">$M_i \cup M_j$</span> is simply <span class="math-container">$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}.$</span> Summing gives us that <span class="math-container">$$c_1+c_2+c_3 \equiv 3n-2f(\sigma_1)-2f(\sigma_2)-2f(\sigma_3) \equiv n \pmod{2}$$</span> as claimed.</p>

<p>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.</p>

<p>Make 3 hexagons, so that <span class="math-container">$G$</span> would have <span class="math-container">$9$</span> 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.</p>

CC BY-SA 4.0
2019-03-13T15:48:40.940Z
sorry, I got confused by the notation while reading your answer in detail :— p is I presume the same as f?
SamiD
CC BY-SA 4.0
2019-03-13T18:46:10.643Z
Ah, yes. I'll change that.
yangpliu
CC BY-SA 4.0
2019-03-13T08:34:54.303Z
2019-03-13T18:46:47.917Z
2019-03-13T18:46:47.917Z
yangpliu
<p>Let <span class="math-container">$G$</span> 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 <span class="math-container">$M_0,M_1,M_2$</span> and let <span class="math-container">$c_0,c_1,c_2$</span> be respectively the number of cycles in <span class="math-container">$M_1\cup M_2, M_2\cup M_0, M_0\cup M_1$</span> respectively. </p>

<p>Is <span class="math-container">$c_0 + c_1 + c_2 \equiv 0 \bmod{2}$</span>? If yes, what is the proof? If not, a counterexample?</p>

<p>Small examples such as a cube or two concentric hexagons with <span class="math-container">$6$</span> cross edges etc. seem to point towards the first possibility but I am not sure either way.</p>

<p>Any references will be greatly appreciated! </p>

CC BY-SA 4.0
2019-03-11T19:57:16.320Z
K_4 is a cubic nonbipartite planar graph where the assertion clearly fails — so bipartiteness is necessary.
SamiD
<reference-request><graph-theory><planar-graphs><matching>
Counting sum of parities of cycle covers in cubic, planar, bipartite graphs
SamiD
# Counting sum of parities of cycle covers in cubic, planar, bipartite graphs

(Asked by: username_0 on 2019-03-11)

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!

**Tags:** reference-request, graph-theory, planar-graphs, matching

> **Comments:**
> **username_0**: K_4 is a cubic nonbipartite planar graph where the assertion clearly fails — so bipartiteness is necessary.  

---

## 1 answers

### Answer by username_1 on 2019-03-13. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: sorry, I got confused by the notation while reading your answer in detail :— p is I presume the same as f?  
> **username_1**: Ah, yes. I'll change that.  

---

