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

-
Since you are new, I want to give some advice about the site: To get the best possible answers, you should explain what your thoughts on the problem are so far. That way, people won't tell you things you already know, and they can write answers at an appropriate level; also, people are much more willing to help you if you show that you've tried the problem yourself. If this is homework, please add the [homework] tag; people will still help, so don't worry. Also, many would consider your post rude because it is a command ("Prove..."), not a request for help, so please consider rewriting it. –  Zev Chonoles Jul 7 '12 at 15:46
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$.