Would a graph with such maximum weighted matchings exist?

2012-11-09T10:25:46Z

Edit Tony's answer is quite nice, but I meant something else. Sorry for editing again, I meant edges.

I am looking for a graph with 3 distinguished edges $xx'$,$yy'$,$zz'$ where $\deg(x)=\deg(y)=\deg(z)=1$.

One can chose arbitrary weights for the edges and the graph must satisfy:

Must have at least two maximum weighted matchings in one of which all of the 3 distinguished edges are present and in the other all are not present.
For all maximum weighted matchings (if more than 2) the distinguished edges are either all present or all not present.

Need this for a graph gadget and suspect it is quite unlikely to exist.

For only 2 distinguished edges a trivial solution is the path with 3 edges $v v' v'' v'''$.

Answer by Tony Huynh for Would a graph with such maximum weighted matchings exist?

2012-11-09T10:59:15Z

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

Would a graph with such maximum weighted matchings exist? - MathOverflow

Would a graph with such maximum weighted matchings exist?

Answer by Tony Huynh for Would a graph with such maximum weighted matchings exist?