Explore BrainMass

Explore BrainMass

    Using the Konig-Egervary Theorem to perform a proof of matching numbers.

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Use the Konig-Egervary Theorem to prove that every bipartite graph G has a matching of size at e(G)/A(G) where A(G) is the maximum degree. Use this to conclude that every subgraph of Kn,n with more than (k-1)n edges has a matching at least k.

    © BrainMass Inc. brainmass.com December 15, 2022, 4:02 pm ad1c9bdddf

    Solution Preview

    Proof. If G is a bipartite graph, by the Konig-Egervary Theorem we know the vertex cover number a(G) is equal to the matching number ...

    Solution Summary

    The Konig-Egervary Theorem is used to perform a proof of matching numbers.