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.

  • $\begingroup$ 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? $\endgroup$ – jp26 May 13 '14 at 6:38
  • 1
    $\begingroup$ @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? $\endgroup$ – Leen Droogendijk May 13 '14 at 9:31
  • $\begingroup$ 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. $\endgroup$ – jp26 May 13 '14 at 11:32

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.

  • $\begingroup$ How is $G^\prime$ $2$-connected? It has a bridge and so a cut-vertex. $\endgroup$ – Casteels May 13 '14 at 10:10
  • $\begingroup$ @Casteels: you are right, I'll delete it for now. $\endgroup$ – Leen Droogendijk May 13 '14 at 10:31
  • $\begingroup$ @Casteels: fortunately the error did not break the entire proof. It should be fixed now. Thanks for your input. $\endgroup$ – Leen Droogendijk May 13 '14 at 10:52
  • $\begingroup$ 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. $\endgroup$ – Casteels May 13 '14 at 11:27
  • $\begingroup$ @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). $\endgroup$ – Leen Droogendijk May 13 '14 at 11:38

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.