3
$\begingroup$

I'm trying to prove that a graph $G$ contains $k$ independent edges iff $q(G-S) \le |S|+|G|-2k$ for all sets $S \subset V(G)$ (where $q(G-S)$ is the odd components). I'm having trouble with verifying whether the following direction is correct though, so, does this look valid for showing that if a graph contains $k$ independent edges, then $q(G-S) \le |S|+|G|-2k$?

Let's assume that the graph $G$ with order $n$ contains $k$ independent edges, and add $n-2k$ vertices that all are adjacent to the vertices in $G$, call this graph G'. Then, we can find a perfect matching in G' by matching each of these $n-2k$ added vertices with the remaining $n-2k$ vertices in $G$ that are unmatched. Then, by Tutte's theorem, we have that q(G'-S) \le |S| for all S \subset G'. Take a subset $S$ of $V(G)$, and also include all the $n-2k$ added vertices to $S$, and call this subset S'. Then q(G'-S') = q(G-S) \le |S'| =|S|+|G|-2k.

1 Answers 1

1

Yes that looks correct to me.

Essentially, G'-S' = G-S.