# Let M be a matching of T, prove that M< N(T) - $\triangle$ (T).

This question is part C of another question:

(a) Using induction on $$n$$, prove that $$T$$ has at least $$\Delta(T)$$ leaves.

(b) Prove that $$B'(T) \geq \Delta (T)$$.

(c) Let $$M$$ be a matching of $$T$$, prove that $$M \leq N(T) - \Delta (T)$$.

Where $$\Delta(T)$$ = Max degree in $$T$$ and $$B'(T)$$ = Size of a minimum edge cover
N(T)= number of vertices in T

Attempt

I have already proved parts a and b, and just need a bit of improvement on part c. Since $$T$$ is an acyclic graph, then it is bipartite. Also, since $$B'(T) + \alpha '(T) = N(T)$$, where $$\alpha'(T)$$ = size of a maximum matching in T, from b we can say that $$\alpha'(T) \leq N(T) - \Delta (T)$$.

The problem is I am not sure if the question is talking about maximum matching or any matching in $$T$$. How can I improve my proof to accommodate any matching in $$T$$?

• If $M$ is a maximum matching in $T$ and $M'$ is any other matching, you should have $|M'| \leq |M|$ by definition. – platty Dec 10 '18 at 5:12
• Okay, I will add it. Is my proof complete then? – Mera Insan Dec 10 '18 at 5:12
• Do you mean to say that $\alpha'(T)$ is the size of a maximum matching and that $B'(T)$ is the size of a minimum edge cover? – platty Dec 10 '18 at 5:15
• Yes, this is what I meant – Mera Insan Dec 10 '18 at 5:16
• You do not define $N(T)$ or $n(T)$. Are these both supposed to be the number of vertices? – platty Dec 10 '18 at 5:20

Your proof seems to be missing the justification for $$B'(T) + \alpha'(T) = N(T)$$. If you have already shown this separately, then this proof would work for an arbitrary matching $$M$$, since for any such matching, $$|M| \leq \alpha'(T)$$.