I recently found the following exercise:
Given a cubic, simple undirected graph $G$ without cut edges, then $G$ is matching covered. I.e. every edge is contained in a perfect matching.
My idea was that, given an edge $e=(u,v)$, I could delete from $G$ the two edges with vertex $u$, say $(u,v_1)$ and $(u,v_2)$, in order to obtain a new graph with:
- $1$ vertex of degree $1$ ($u$ itself)
- $2$ vertices of degree $2$ ($v_1$ and $v_2$)
- any other vertex of degree $3$.
Then, using the Tutte theorem, I am trying to prove the existence of a perfect matching in this new graph as this would be a perfect matching for $G$ containing $e$.
Does anyone have some sorts of advice about that?