Hall's theorem revisited (Q2723513)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Hall's theorem revisited |
scientific article; zbMATH DE number 1614783
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Hall's theorem revisited |
scientific article; zbMATH DE number 1614783 |
Statements
5 July 2001
0 references
matching
0 references
Hall's theorem
0 references
0 references
0 references
0 references
0 references
0.8814814
0 references
Hall's theorem revisited (English)
0 references
The author gives a short inductive proof of Hall's well-known theorem about matchings in bipartite graphs. Using a simple directed graph in his argument he estimates the number of ways to extend a given matching which is not maximum by one edge. Since this number is always positive provided Hall's well-known condition on the cardinality of the neighbourhoods is satisfied, Hall's theorem follows. Like in R. Rizzi's recent proof of König's theorem about matchings in bipartite graphs [J. Graph Theory 33, No.~3, 138-139 (2000)] the argument is short and elegant.
0 references
