Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Just to clarify, by $vv'v''$ you mean a path with three edges, not three vertices right? –  Tony Huynh Nov 9 '12 at 10:44
    
@Tony yes, indeed I mean three edges, thank you. –  joro Nov 9 '12 at 10:51
    
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. –  Tony Huynh Nov 9 '12 at 12:22

1 Answer 1

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

share|improve this answer
    
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? –  joro Nov 9 '12 at 11:27
    
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. –  Tony Huynh Nov 9 '12 at 11:35
    
$C_4$ (and $C_{2k}$) with weights 1 have exactly 2 maximum weighted matchings satisfying the question without deg. 1 restriction. –  joro Nov 9 '12 at 11:35
    
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$. –  Tony Huynh Nov 9 '12 at 11:39
    
You are right, sorry. I screwed the question :-(. I meant to ask about distinguished edges with one vertex of degree $1$. Sorry again :( –  joro Nov 9 '12 at 11:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.