Property of maximum matching

1k Views Asked by At

Let $G=(V,E)$ be a graph with no perfect matching. Then there exists a vertex $v$ such that every incident edge (i.e., every edge incident to $v$) is part of a maximum matching.

I'm not sure how to prove this. How can every edge that coincides with $v$ be part of a maximum matching? It sounds contrary to the definition of matchings.

1

There are 1 best solutions below

2
On BEST ANSWER

This proof works for finite graphs only.

Suppose contrary that, for every $v\in V$, there exists an edge $e_v=\left\{v,w_v\right\}$, where $w_v\in V$, such that $e_v$ is not a part of any maximum matching in $G$. Let $M$ be a maximum matching in $G$.

Since $G$ has no perfect matchings, there is a vertex $v\in V$ not matched in $M$. Note that $w_v$ has to be matched in $M$; otherwise $M\cup\left\{e_v\right\}$ would be a matching in $G$ strictly larger than $M$. Suppose that, in $M$, $w_v$ is paired with $u\in V$. Define $M':=\Big(M\setminus\big\{\left\{w_v,u\right\}\big\}\Big)\cup\left\{e_v\right\}$. Then, $M'$ is a matching in $G$ containing $e_v$ such that $\left|M'\right|=|M|$, whence $M'$ is a maximum matching. Thus, $e_v$ is a part of a maximum matching, a contradiction. That is, there must exist a vertex in $G$ each of whose incidental edges belongs in a maximum matching in $G$.