Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $G$ be a graph with $p$ vertices, with minimum degree $d$. Suppose $d \leq p/2$. Prove that $G$ has a matching of size at least $d$.

Any advice on how to approach this question?

I'm trying to do it with (strong) induction:

Show it holds for base case $p=1$ (this is trivial).

Induction Hypothesis: Assume $p > 1$. For any $p' < p$, A graph of $p'$ vertices with minimum degree $d \leq p'/2$ has a matching of size at least $d$.

Now, consider a graph $G$ with min degree $d$ and $p$ vertices. Pick a vertex $v$ in $G$ such that the mindeg(G-v) = d. Case 1: $d < p/2$. Case 2: $d = p/2$.

Case 1: Now, G-v is a graph. G-v has min deg $d$. G-v has $p' < p$ vertices. $d \leq p'/2$. Now, by the induction hypothesis, G-v has a matching of size $d$. Then clearly, $G$ has a matching of size $d$ since adding a vertex and more edges will not reduce the matching's validity or size.

Case 2: ??

share|improve this question

1 Answer 1

Try induction on $d$ instead.

But don't think in terms of induction, think in terms of graphs. Try to understand why the claim is true for $d = 1$, why it's true for $d = 2$, why for $d = 3$. If you can figure out these cases you can probably come up with an inductive argument.

Did you notice that $p \geq 2d$ is a necessary condition for the existence of a matching of size $d$?

One common approach for proving theorems of this general nature, showing that there exists some object of size $X$ given some conditions, is to construct the elements of the object one by one. That's why induction on $d$ is a-priori more appropriate here.

Your partial argument doesn't address the problem at all. The case $d < p/2$ you handled is exactly the case which requires no reasoning. So you haven't done much more than just write out the general form of an inductive argument. The reason is that inducting on $p$ just doesn't work. Next time, don't give up so fast, try induction on all relevant parameters, as well as other proof methods. For each of them you should be able to write this kind of skeleton pretty fast, and concentrate on the non-schematic part.

share|improve this answer

Your Answer

 
discard

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.