1
$\begingroup$

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:

  1. 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.
  2. 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'''$.

Improve this question
$\endgroup$
3
  • $\begingroup$ Just to clarify, by $vv'v''$ you mean a path with three edges, not three vertices right? $\endgroup$
    – Tony Huynh
    Commented Nov 9, 2012 at 10:44
  • $\begingroup$ @Tony yes, indeed I mean three edges, thank you. $\endgroup$
    – joro
    Commented Nov 9, 2012 at 10:51
  • $\begingroup$ As I mention in the comments, the same proof also answers your edited question. I added a proof, but it is really just a cut and paste job. $\endgroup$
    – Tony Huynh
    Commented Nov 9, 2012 at 12:22

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you. Are you sure this works if x,y,z are not of degree 1? I think I found a lot of graphs with exactly 2 perfect matchings (weights 1) and the they satisfy my question except for degree 1? $\endgroup$
    – joro
    Commented Nov 9, 2012 at 11:27
  • $\begingroup$ If all weights are 1 and the graph has a perfect matching, then every maximum weight matching will be a perfect matching and hence cover $x,y,z$. So condition (1) will not be satisfied. Not relevant, but this proof also shows that the only graph with exactly two perfect matchings is an even cycle. $\endgroup$
    – Tony Huynh
    Commented Nov 9, 2012 at 11:35
  • $\begingroup$ $C_4$ (and $C_{2k}$) with weights 1 have exactly 2 maximum weighted matchings satisfying the question without deg. 1 restriction. $\endgroup$
    – joro
    Commented Nov 9, 2012 at 11:35
  • $\begingroup$ See my comment above. Your examples do not satisfy condition (1), since there cannot be a maximum weight matching which avoids $x,y,z$ for any choice of $x,y,z$. $\endgroup$
    – Tony Huynh
    Commented Nov 9, 2012 at 11:39
  • $\begingroup$ You are right, sorry. I screwed the question :-(. I meant to ask about distinguished edges with one vertex of degree $1$. Sorry again :( $\endgroup$
    – joro
    Commented Nov 9, 2012 at 11:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .