This chapter is devoted to bipartite graphs which have the property that any subset of vertices, from one of the colour classes, has a neighbour set which is at least as large as itself, be it by some additive or multiplicative factor. We shall see that such graphs have a very useful structure, and a variety of applications.

Graphs with Hall's condition

We begin by considering bipartite graphs with bipartition (V1, V2) which satisfy the condition |N(A)| ≥ |A| for every A ⊆ V1 (where N(∅) = ∅). Graphs with this property arise very often in practice. Many practical problems can be reformulated as problems about finding a matching M such that every vertex in V1 is incident with an edge in M. Such a matching is called a matching of V1 into V2. The ‘marriage problem’, which we have already considered in Section 5.1, is one of many examples.

It is clear that for us to hope to find a matching of V1 into V2 we must have |N(A)| ≥ |A| for every A ⊆ V1. Remarkably, as the following result of Philip Hall (1935) shows, this condition is also sufficient.

Theorem 6.1.1 (Hall's Theorem) Let G be a bipartite graph with bipartition (V1, V2). Then G has a matching of V1 into V2 if and only if |N(A) ≥ |A| for every A ⊆ V1.