Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Version 1

Is there a connected graph containing edges $e_1, e_2, e_3$ such that there is a perfect matching containing any two of the edges but no perfect matching containing all three?

EDIT: Brian M. Scott provides a nice example in his answer.

Version 2

Is there a connected graph in which any two nonincident edges belong to a perfect matching but there are three edges such that no perfect matching contains all three?

EDIT: I provide an example in my answer.

share|improve this question
add comment

3 Answers 3

For Version 1:

                         *  
                        /|\  
                       / | \  
                      *  *  *  
                      |  |  |  
                      *  *  *  
                       \ | /  
                        \|/  
                         *  

The three parallel edges in the middle are $e_1,e_2$, and $e_3$. Once you use two of them in a perfect matching, you’re forced to complete the matching by using the edges from the top and bottom vertices to the ends of the third of them. (After working this out, I realized that it fits Vhailor’s description, but I’m offering it anyway, since it’s considerably more explicit.)

share|improve this answer
add comment

It's not too hard to construct an example to "version 1". The fact that every subset of two is part of a perfect matching tells you that there can't be a vertex that is adjacent to two of $e1,e2,e3$. So start by drawing these three, and then complete the example by adding two other vertices and making sure that they aren't connected by an edge to prevent the perfect matching with $e1,e2$ and $e3$ while making sure that there is one for any subset of $2$.

share|improve this answer
add comment
up vote 0 down vote accepted

The 3-dimensional hypercube is an example for both versions. A short case analysis (omitted) shows that any two edges can be extended to a perfect matching, but no perfect matching contains $\{e_1, e_2, e_3 \}$, where $$ \begin{align*} e_1 &= (0,0,0)(0,0,1)\\ e_2 &= (1,0,0)(1,1,0)\\ e_3 &= (0,1,1)(1,1,1), \end{align*} $$ as the remaining two unmatched vertices are the antipodes $(0,1,0)$ and $(1,0,1)$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.