This exercise can be found in "Graph Theory" by Bondy and Murty. I need some help in order to complete the proof. If you have other idea, share us pls.
Only must you use the Berge's Theorem.
16.1.12
Let $G$ be a simple graph with $n\geq2\delta$. Show that $\alpha'\geq \delta$.
First by contradiction suppose that $\alpha'< \delta$. It is easy to see that the vertex cover by $M^ \ast $ such that $M^ \ast $ is a maximum matching is $2(\delta-1) \leq n-2$ (1). Now at least there are 2 vertex ($u,v$) that are not cover by $M$. If these vertex are adjacent, we win. If not the set $I = {u,v}$ is independent.
Let defined $M_u$ the set of edges of $M^ \ast $ such that these edges are incident to $N(u)$.
- If $M_u = M_v$, i.e, $N(u) = N(v)$ (If there is a $x$ in $N(u)$ and $N(v)$ we win)
The vertexes in $N(N(u))$ form an independent set $I'$(if not we should find an augmented path). They have neighborhoods cover by $M^\ast$, (if not we can find an augmented path), hence $M_{N(I')\ N(N(u))}$ at least is one. Contradiction because $|M^\ast|<\delta$ and we sum up that $|M^\ast| \geq \delta$
If $M_u \cap M_v = \emptyset$ is not hard to see that there is al least one from $N(u)$ or $N(v)$ is not covered.
If $M_u \cap M_v = \emptyset$. Here I need help or some hint.