# Maximum Matching of a graph versus its minimum degree

I'm trying to do the next problem, it seems easy but I can't do it!

Let G be a simple graph with $n\geq 2\delta$. Show that $\alpha' \geq \delta$

where

$\delta=$minimum degree in $G$

$\alpha'=$ the number of edges in a maximum matching of $G$

and $n$ the number of vertices of G.

I thought this: if $M$ is a maximum matching of $G$ and suppose $|M| < \delta$, then, somehow show that any two vertices not covered by M are connected by an M-augmenting path and derive a contradiction, but, even this, I can't see how to do it.

Any help would be appreciated! Thanks!

Let $G$ be a simple graph (non necessarily finite—see postcript) with minimum degree $\delta$ and order $|V(G)|\ge2\delta.$ Let $M$ be a maximum matching in $G,$ and assume for a contradiction that $|M|=m\lt\delta.$
Then $W=V(G)\setminus V(M)$ is independent and $|W|\ge2.$ Choose two distinct vertices $x,y\in W.$ There are at least $2\delta$ edges between $V(M)$ and $\{x,y\}.$ Since $2m\lt2\delta,$ we can choose an edge $uv\in M$ such that there are at least three edges between $\{u,v\}$ and $\{x,y\}.$ Without loss of generality, we can assume that two of those edges are $ux$ and $vy.$ Then $M-uv+ux+vy$ is a matching in $G$ of size $m+1,$ contradicting our assumption that $M$ is a maximum matching.
P.S. What if $G$ is an infinite graph? If $\delta$ is an infinite cardinal, then any maximal matching has cardinality at least $\delta.$ (The axiom of choice is assumed.) If $\delta$ is finite, and if there is no matching of size $\delta,$ then there is a maximum matching, and the argument above is fine.