Characterizations and Notes
König's theorem states that, in bipartite graphs, the maximum matching is equal in size to the minimum vertex cover. Via this result, the minimum vertex cover, maximum independent set, and maximum vertex biclique problems may be solved in polynomial time for bipartite graphs.
The marriage theorem (or Hall's Theorem) provides a characterization of bipartite graphs which have a perfect matching and the Tutte theorem provides a characterization for arbitrary graphs.
A perfect matching is a spanning 1-regular subgraph, a.k.a. a 1-factor. In general, a spanning k-regular subgraph is a k-factor.
Read more about this topic: Matching (graph Theory)
Famous quotes containing the word notes:
“Or bid the soul of Orpheus sing
Such notes as, warbled to the string,
Drew iron tears down Pluto’s cheek,
And made Hell grant what love did seek;”
—John Milton (1608–1674)