1
$\begingroup$

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: ??

1 Answers 1