How To Find A Perfect Match


This article presents a script that finds a perfect match in any bipartite graph or shows why one cannot exist.


Recall that a bipartite graph is any undirected graph [1] where its nodes (or vertices) can be partitioned into two sets, and where edges only exist between those two sets. For this article, those sets are equal in size.

For example, consider the following bipartite graph:

The goal is to find a perfect match, which is a collection of edges sharing no nodes and for which every node is part of some edge in that collection.