Hall's marriage theorem

Hall’s Marriage Theorem

• Hall’s Marriage Theorem is a central theorem of combinatorics and graph theory which determines whether a perfect matching is possible.
• A perfect matching, also known as a complete matching, is when each vertex of the graph is connected to exactly one edge.
• The theorem is often described in terms of a bipartite graph, however, it can be generalised to other types of graphs.

The Theorem

• The theorem was proposed by mathematician Philip Hall. It states that, for a finite bipartite graph, a complete matching is possible if and only if, for any subset of vertices, the number of vertices in that subset is less than or equal to the number of vertices in its neighbourhood.
• The neighbourhood of a vertex or set of vertices is the collection of vertices connected to the initial vertex or vertices by at least one edge.

Practical Implications

• This theorem has wide applications in combinatorial problems of arranging, choosing and distributing objects to each other.
• It has great use in the fields like network flows, allocation and scheduling problems.
• The “Marriage problem”, where the theorem derives its name, is an example of the application. In this scenario, the theorem can be used to determine if it’s possible to pair off a group of women and men (assuming that every person must marry someone of the opposite gender) according to their preferences.

Representation

• Hall’s marriage theorem can be represented by using the Hall’s condition. The condition is that for every subset of vertices, the number of vertices in that subset (

  A

  ) must be less than or equal to the number of vertices in its neighbourhood (

  N(A)

  ). This is mathematically represented as

  A

  ≤

  N(A)

  .

By understanding Hall’s Marriage Theorem and remembering to check the Hall’s condition, you can tackle a wide range of combinatorial problems.