The marriage problem Ina certain community every boy knows exactly k girls and every girl knows exactly k boys. Show that every boy can marry a girl he knows and vice versa. (Construct a k-regular...

The marriage problem

Ina certain community every boy knows exactly k girls and every girl knows exactly k boys. Show that every boy can marry a girl he knows and vice versa.

(Construct a k-regular bipartite graph in which each edge signifies that a boy (represented by one end-point) knows a girl (represented by the other end-point). The problem then reduces to showing that any k­ regular bipartite graph, k > 0, has a perfect matching. Show that the number of boys must equal the number of girls and that the graph

satisfies Hall's theorem (exercise 5.3). The result then follows.)