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$


$\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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.