# On independent set of edges included in a perfect matching.

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.

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.
• $S$ may not [actually, does not] cover every vertex in $L$ but $S'$ does. And that is what you need: $S'$ to cover every vertex covered by $S$ [and perhaps two more] – Mike Nov 25 '18 at 11:25