Hall's theorem revisited (Q2723513)

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.