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.
Best 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.