marriage problem

Show Summary Details

Quick Reference

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.

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.