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.

  • 3
    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.2012-07-07
  • 0
    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$2012-07-07
  • 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$.