3
$\begingroup$

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?

$\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.