Skip to main content
2 of 3
Corrected the path with 3 edges
joro
  • 25.4k
  • 10
  • 66
  • 121

Would a graph with such maximum weighted matchings exist?

I am looking for a graph with 3 distinguished vertices of degree $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 vertices are present and in the other all are not present.
  2. For all maximum weighted matchings (if more than 2) the distinguished vertices 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 vertices a trivial solution is the with 3 edges $v v' v'' v'''$.

joro
  • 25.4k
  • 10
  • 66
  • 121