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


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
    $\begingroup$ If $M$ is a maximum matching in $T$ and $M'$ is any other matching, you should have $|M'| \leq |M|$ by definition. $\endgroup$ – platty Dec 10 '18 at 5:12
  • $\begingroup$ Okay, I will add it. Is my proof complete then? $\endgroup$ – Mera Insan Dec 10 '18 at 5:12
  • $\begingroup$ 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? $\endgroup$ – platty Dec 10 '18 at 5:15
  • $\begingroup$ Yes, this is what I meant $\endgroup$ – Mera Insan Dec 10 '18 at 5:16
  • $\begingroup$ You do not define $N(T)$ or $n(T)$. Are these both supposed to be the number of vertices? $\endgroup$ – 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)$.

  • $\begingroup$ Yes, I proved that. Thanks for your help $\endgroup$ – Mera Insan Dec 10 '18 at 5:31

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.