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

21 Views Asked by At

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

1

There are 1 best solutions below

1
On BEST ANSWER

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)$.