Hall violator
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem. Formally, given a bipartite graph , a Hall-violator in is a subset of , for which , where is the set of neighbors of in . If is a Hall violator, then there is no matching that saturates all vertices of .
Therefore, there is also no matching that saturates . Hall's marriage theorem says that the opposite is also true: if there is no Hall violator, then there exists a matching that saturates .
In graph theory, a Hall violator is a set of vertices in a graph, that violate the condition to Hall's marriage theorem. Formally, given a bipartite graph , a Hall-violator in is a subset of , for which , where is the set of neighbors of in . If is a Hall violator, then there is no matching that saturates all vertices of .
Therefore, there is also no matching that saturates . Hall's marriage theorem says that the opposite is also true: if there is no Hall violator, then there exists a matching that saturates .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1285189811 under CC BY-SA 4.0; modifications have been made.