Using the Konig-Egervary Theorem to perform a proof of matching numbers.
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 February 24, 2021, 2:12 pm ad1c9bdddfhttps://brainmass.com/math/discrete-math/konig-egervary-theorem-perform-proof-matching-numbers-7189
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.
$2.19