My question:

  1. In bridgeless cubic graph $G$, given an edge $e_1$ in $G$, Prove that there exist a perfect matching contain the given edge $e_1$.

  2. Given two edges $e_1,e_2$ with the distance between $e_1$ and $e_2$ is $1$, that is to say, there is an edge $e_3$ such that $e_1e_2e_3$ compose a path. Is there a perfect matching in $G$ contains $e_1$ and $e_2$?

  3. For arbitrary two edges $e_1$ and $e_2$, do there exist a perfect matching contains $e_1,e_2$?

Comment: for Question 1, I have proved it using Tutte's matching theorem, a similar technique with the prove of existence of perfect macthing. For Question 2: there is a counterexample. But I wonder, could we enhence the condition such that the conclusion holds?


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.