Here is a problem I'm trying to solve:
Let $G$ be a graph on at least $2k+2$ vertices which has a perfect matching. Show that if every set of $k$ independent edges is included in a perfect matching then every set of $kâ1$ independent edges is included in a perfect matching.
Here is my attempt:
By tutte berge theorem: $comp(G\ X) â¤|X|+|V(G)|â2k$ if and only if $G$ has a matching of size $k$.
Ok So I assume a perfect matching in $G$ has size at least $k$.
Let $S$ be a set of independent edges of size $k-1$, suppose it is not in a set of independent edges of size $k$, then every other edges in $G$ is incident to an end vertices of edges in $S$. But then $S$ could not be inside of a perfect matching of size at least $k$? What is wrong here?
Help, you can also give a complete solution.
Best Answer
Well, you would be done if you could extend every set $S$ of $k-1$ independent edges to a set of $k$ independent edges [make sure you see why]. And in fact you can.
Let $M$ be a perfect matching. Then $M \cup S$ contains at least one path or cycle $L$ with an odd number $\ell$ of edges such that only $\lfloor \frac{\ell}{2}\rfloor$ of those edges are in $S$ and the remaining $\lfloor \frac{\ell}{2}\floor +1$ are in $M$. So let $S' = S - (S\cap L) + (M \cap L)$. Then (a) $S'$ is an independent set with $k-1+1 =k$ edges, and (b) every vertex covered by $S$ is also covered by $S'$ [make sure you see why for both (a) and (b)].
Then, as $G$ has a perfect matching and at least $2k+2$ vertices, a perfect matching in $G$ has $k+1$ edges. Because $G$ also has the property that every independent set of $k$ edges can be extended to a perfect matching, this implies that there is a perfect matching containing $S'$ that has at least one edge $e$ not in $S'$. Then $\{e\}+S'$ is an independent set of edges. Therefore, as every vertex covered by $S$ is also covered by $S'$, it follows that $\{e\}+S$ is also an independent set of edges with $e$ not be in $S$ [make sure you see why]. So $S$ indeed can be extended to an independent set of $k$ edges, giving the desired result.