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:
“The drama critic on your paper said my chablis-tinted hair was like a soft halo over wide set, inviting eyes, and my mouth, my mouth was a lush tunnel through which golden notes came.”
—Samuel Fuller (b. 1911)