Let $G=(V,E)$ be a finite, simple, undirected graph. We say that a matching $M\subseteq E$ is a maximum matching if for all $e\in (E\setminus M)$ the set $M\cup\{e\}$ is not a matching any more.


Maximum matches can have different sizes.


**Question**. Is there a positive integer $k\in\mathbb{N}$ such that for all finite graphs $G=(V,E)$ and all maximum matchings $M\_1, M\_2\subseteq E$ we have $|M\_1|-|M\_2| \leq k$? If yes, what is the value of $k$?



Sizes of maximum matchings in a finite, simple, undirected graph
Let $m^-, m^+$ be the sizes of a smallest and largest maximal matching respectively. The best possible inequality you can prove in general is that $m^- \geq m^+/2$.


To see that this inequality is true, let $M$ be a maximum matching and let $M'$ be any other maximal matching. Then every edge of $M$ meets an edge of $M'$, else we could extend $M'$ using an edge from $M$. But each edge of $M'$ meets at most $2$ edges of $M$, so $|M'| \geq |M|/2$.


To see that this inequality is best possible, it suffices construct a graph in which the above argument is tight. So start with a matching $M$ with an even number of edges and add a second matching $M'$ such that every edge of $M'$ meets two edges of $M$ and no edge of $M$ meets more than one edge of $M'$. Explicitly, this graph is a vertex-disjoint union of paths of length $3$.


