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 germ of violence is laid bare in the child abuser by the sheer accident of his individual experience ... in a word, to a greater degree than we like to admit, we are all potential child abusers.”
—F. Gonzalez-Crussi, Mexican professor of pathology, author. “Reflections on Child Abuse,” Notes of an Anatomist (1985)