Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer

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|cite|improve this answer
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|cite|improve this answer

Your Answer


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.