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:
“Ceremony and ritual spring from our heart of hearts: those who govern us know it well, for they would sooner deny us bread than dare alter the observance of tradition.”
—F. Gonzalez-Crussi, Mexican professor of pathology, author. “On Embalming,” Notes of an Anatomist (1985)