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?


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.