0
$\begingroup$

Let $G$ be a loopless graph with no isolated vertices. Let $X$ be a largest matching in $G$ and let $Y$ be a smallest set of edges of $G$ so that every vertex of $G$ is incident with at least 1 edges in $Y$. How can we prove that $|X| + |Y|=|V(G)|$?

My rigor is a little clouded here. If you could show me all the steps in the proof that would be great. I am unable to conceive a picture of this. I think that is causing most of my confusion.

  • 0
    vertices, yes. It is a maximal matching.2012-07-07

1 Answers 1

2

EDIT 9 July 2012: I found a solution here. It goes like this:

Let $X$, a largest matching, have $n$ edges. Let $Z$ have all the edges of $X$, together with one edge incident to each vertex left unmatched by $X$. Then $|Z|=v-|X|$, where $v$ is the number of vertices of $G$, because $Z$ has one edge for each vertex of $G$ except that the edges in $X$ take care of two vertices each. Also, every vertex of $G$ is incident to at least one edge in $Z$, so $|Y|\le|Z|=v-|X|$.

Now let $Y$ be as in the hypothesis. Its minimality implies it has no cycles. So $Y$ is a union of disjoint trees. Let $W$ contain one edge from each tree. Then $W$ is a matching, and the number of edges in $W$ is the number of trees in $Y$, which is $v-|Y|$, since every tree has one more vertex than it has edges. So, $|X|\ge|W|=v-|Y|$.

So we have proved $|X|+|Y|\le v$, and $|X|+|Y|\ge v$.