Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. 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
up vote 2 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.