1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.