1
$\begingroup$

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.

3 Answers 3

0

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

1

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.)

0

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