If I have: matching $M$ which matches all vertices of $A$ matching $M'$ which matches all vertices of $B$
Where $|A| < |B|$ and $A$ and $B$ are two independent sets
I created a subgraph of the vertices in A and B and their edges and their neighbours.
Can I then prove that $A$ can be extended by an element in $B\setminus A$?
I think I know that $M$ is not a maximum cardinality matching because obviously $|M| < |M|'$, so this tells me that the graph must contain an $M$-augmenting path. But I dont know how to use this to prove that $A$ can be extended?
Let's go to say that $G$ is the graph cited above. Considerer $M_1 = M-M'$ and $M_2 = M'-M$. Since $|M| < |M'|$, then $|M_1| < |M_2|$ and $M_1$ is not maximum matching in $G[M_1 \cup M_2]$. By Berge's theorem, exists a $M_1$-augmenting path $P$ in $G[M_1 \cup M_2]$. Thus, exists a vertice $a \in B-A$ such that $M \Delta E(P)$ matches all vertices in $A \cup a$. Therefore, we have the increasing property is valid.