Skip to main content
3 of 3
added 822 characters in body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Such a gadget does not exist.

Proof for original vertex version. Suppose such a graph $G$ exists. Let $x,y$, and $z$ be the distinguished vertices. Let $M_1$ be a maximum weight matching which covers $x,y,z$, and let $M_2$ be a maximum weight matching which avoids $x,y,z$. Suppose the edges of $M_1$ of $M_2$ are coloured red and blue respectively. Consider $M_1 \triangle M_2$. Every component of $M_1 \triangle M_2$ is either a path or an even cycle. Since each of $x,y,z$ is covered by $M_1$ but not by $M_2$, $x,y,z$ are endpoints of path components of $M_1 \triangle M_2$. There must exist a component of $M_1 \triangle M_2$ which contains exactly one of $x,y,z$. Switching red and blue edges along this path produces another maximum weight matching which violates condition (2).

Note that this proof does not actually assume that $x,y,z$ are of degree 1.

Proof for edited edge version. Suppose such a graph $G$ exists. Let $x,y$, and $z$ be the distinguished edges. Let $M_1$ be a maximum weight matching which contains $x,y,z$, and let $M_2$ be a maximum weight matching which is disjoint from $x,y,z$. Suppose the edges of $M_1$ of $M_2$ are coloured red and blue respectively. Consider $M_1 \triangle M_2$. Every component of $M_1 \triangle M_2$ is either a path or an even cycle. Since each of $x,y,z$ is adjacent to a degree 1 vertex, each of $x,y$ and $z$ must be end edges of path components of $M_1 \triangle M_2$. There must exist a component of $M_1 \triangle M_2$ which contains exactly one of $x,y,z$. Switching red and blue edges along this path produces another maximum weight matching which violates condition (2).

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187