Size of matching
pProve that every graph G without isolated vertices has a matching of size
at least n(G)/(1+∆(G)). (Hint: Apply induction on e(G))./p pI know
that a perfect matching is the size of a minimum edge cover, but I don't
really think that relates to this problem. I have no idea where to go with
it./p
No comments:
Post a Comment