# 3-connected Cubic graph matching

I've been doing some recreational graph theory, and I've come across a problem that I can't seem to figure out.

Problem: Let e be an edge of a 3-connected cubic graph G. Prove that there exists a perfect matching that covers e.

Now, I know that any bridgeless cubic graph has some perfect matching (Peterson's theorem, which follows from the Tutte-Berge formula), but I don't see a natural extension to 3-connected cubic graphs. My first thought is to delete u & v (if e = {u, v}), but then you just have a connected graph that you're trying to cover with a perfect matching. My other thought is that you could delete the other two edges still incident with (WLOG) v, since a 3-connected graph is at least 3-edge-connected (in this case, exactly 3-edge connected), but that still doesn't get me anywhere. Any hints or steps in the right direction would be helpful.

• We can suppose that $e$ isn't in the known perfect matching $M$, since we would be done. What can you say about $G$ with the edges of $M$ deleted? – jp26 May 13 '14 at 6:38
• @jp26: Can you elaborate on this? Your hint suggests a solution that is much simpler than mine, but how do you finish the proof if $e$ happens to be on an odd cycle of the remaining 2-factor? – Leen Droogendijk May 13 '14 at 9:31
• I was just suggesting an alternate approach that might be fruitful; the cases that are left are snarks and they have "oddness" at least 2. – jp26 May 13 '14 at 11:32

## 1 Answer

Let $e=uv$ be an edge of $G$. Let $f$ and $g$ be the other two edges incident with $v$. Let $G'=G-f-g$.

Claim 1: $G'-v$ is 2-connected.

$G'-v$ is the same as $G-v$.

Claim 2: $G'$ has a perfect matching.

You can prove this by showing directly that the Tutte condition holds. I assume that you are familiar with the standard proof of Petersen's theorem, so I will not elaborate on every detail. Note that $G'$ has only 2 vertices of even degree.

Let $S$ be a vertex subset of $G$, $o(G'-S)$ the number of odd components of $G'-S$. At most one odd component can contain $v$; that component can have as few as 1 edge to $S$ (since $G'$ is still connected). All other odd components contain a vertex different from $v$, so because $G'-v$ is 2-connected all other odd components have at least 2 edges to $S$. At most two odd components can contain a vertex of even degree (even in $G'$). All other odd components must have at least three edges to $S$ (as in the standard proof of the Petersen theorem).

Let $x$ be the number of edges between $S$ and the odd components of $G'-S$. We have just shown that $x\geq 3o(G'-S)-4$.

On the other hand $S$ can accomodate at most $3|S|$ edges, so $x\leq3|S|$.

This means that $o(G'-S)\leq|S|+\frac{4}{3}$.

Now finally use the fact that $G$ is even, so $o(G'-S)$ and $|S|$ have the same parity. This shows that $o(G'-S)\leq|S|$ and the Tutte condition holds.

Final argument: the perfect matching of $G'$ is a perfect matching of $G$ and it contains $e$, since the degree of $v$ in $G'$ is 1.

• How is $G^\prime$ $2$-connected? It has a bridge and so a cut-vertex. – Casteels May 13 '14 at 10:10
• @Casteels: you are right, I'll delete it for now. – Leen Droogendijk May 13 '14 at 10:31
• @Casteels: fortunately the error did not break the entire proof. It should be fixed now. Thanks for your input. – Leen Droogendijk May 13 '14 at 10:52
• Won't the perfect matching in $G^\prime$ cover $w$ and so you can't just add $e$ to it? Does your argument break if you just delete both $v$ and $w$ from $G$ in the first place? I haven't checked but it seems a natural thing to try. – Casteels May 13 '14 at 11:27
• @Casteels: Your first question makes no sense to me (even if I replace $w$ by $v$). Regarding your second question: that indeed was my first approach, but I gave it up rather quickly (which not necessarily means that it does not lead to anything, just that I did not see it before the next try that did lead to a result). – Leen Droogendijk May 13 '14 at 11:38