Consider $G$ is a connected graph. For any vertex $v$ in $G$, prove that there exists a matching for which $v$ is saturated.

382 Views Asked by At

I couldn't think of any connected graphs where the property didn't hold, so assume it is true. However, I couldn't think of a formal proof. I tried doing this:

Case I: If $G$ has an even number of vertices, then the maximum matching is a perfect matching, so the property holds.

Case II: If $G$ has an odd number of vertices, then there is no perfect matching, so there must be a vertex not saturated by the maximum matching.... This is the part I am stuck in, I cannot think of a way I can show that it is possible to saturate each vertex by different maximum matchings. How do I show that a graph can have multiple maximum matchings?

1

There are 1 best solutions below

5
On

Answer for modified question:

This is trivial true. For each vertex just take a maximal matchings that contains that vertex. You don't need even connectivety, just every vertex should have degree at least 1.


No, take graph: $u-v-w$ then maximal we have only 2 maximal matchings:

  • matching is $u-v$ and $w$ is not saturated
  • matching is $v-w$ and $u$ is not saturated.

Even if graph has even vertices it does not hold. Take a graph with 4 vertices $a,b,c, d$ and edges $a-d$, $b-d$ and $c-d$. In this case only $d$ and one of $a,b,c$ are saturated while other two not, for any maximal matching.