# Loopless graph-proof

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.

-
I'm a little confused as to what $X$ is. 'Largest matching in $G$' Largest matching of what? I'm inferring that you mean vertices, but are there any conditions to what vertices should be matched? Otherwise I would just interpret $X$ as the vertices of $G$ – Russ Jul 7 '12 at 16:07
vertices, yes. It is a maximal matching. – Xuan Huang Jul 7 '12 at 16:31

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$.