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