marriage problem

views updated

marriage problem In a certain community every boy knows exactly k girls and every girl knows exactly k boys. The problem is to show that every boy can marry a girl he knows and vice versa. This problem is a case of showing that any bipartite graph whose vertices all have the same nonzero number of edges incident to it has a perfect matching.

More From encyclopedia.com