Would a graph with such maximum weighted matchings exist? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T00:49:05Z http://mathoverflow.net/feeds/question/111886 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111886/would-a-graph-with-such-maximum-weighted-matchings-exist Would a graph with such maximum weighted matchings exist? joro 2012-11-09T10:25:46Z 2012-11-09T12:20:12Z <p><strong>Edit</strong> Tony's answer is quite nice, but I meant something else. Sorry for editing again, I meant edges.</p> <p>I am looking for a graph with 3 distinguished edges \$xx'\$,\$yy'\$,\$zz'\$ where \$\deg(x)=\deg(y)=\deg(z)=1\$.</p> <p>One can chose arbitrary weights for the edges and the graph must satisfy:</p> <ol> <li>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.</li> <li>For all maximum weighted matchings (if more than 2) the distinguished edges are either all present or all not present.</li> </ol> <p>Need this for a graph gadget and suspect it is quite unlikely to exist.</p> <p>For only 2 distinguished edges a trivial solution is the path with 3 edges \$v v' v'' v'''\$.</p> http://mathoverflow.net/questions/111886/would-a-graph-with-such-maximum-weighted-matchings-exist/111889#111889 Answer by Tony Huynh for Would a graph with such maximum weighted matchings exist? Tony Huynh 2012-11-09T10:59:15Z 2012-11-09T12:20:12Z <p>Such a gadget does not exist.</p> <p><strong>Proof for original vertex version.</strong> 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). </p> <p>Note that this proof does not actually assume that \$x,y,z\$ are of degree 1. </p> <p><strong>Proof for edited edge version.</strong> 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). </p>