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:
“I am thankful for small mercies. I compared notes with one of my friends who expects everything of the universe, and is disappointed when anything is less than best, and I found that I begin at the other extreme, expecting nothing, and am always full of thanks for moderate goods.”
—Ralph Waldo Emerson (1803–1882)