This is documentation for Mathematica 6, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.1)


gives the maximal matching of the bipartite graph g.
  • MaximalBipartiteMatching gives a maximal set of non-adjacent edges between the two vertex sets of the bipartite graph.
  • The bipartite graph represented by an m×n matrix consists of the row and column vertex sets R={1, 2, ..., m} and C={1, 2, ..., n}, with a vertex iR and jC connected if the matrix element gij≠0.
  • The bipartite graph represented by a rule list {i1->j1, i2->j2, ...} consists of vertex sets R=Union[{i1, i2, ...}] and C=Union[{j1, j2, ...}], with a vertex iR and jC connected if the rule i->j is included in the rule list.
  • MaximalBipartiteMatching returns a list of index pairs {{i1, j1}, ..., {ik, jk}} where the number of pairs k is not larger than either vertex set.
A bipartite graph describing acceptable drinks for 4 people:
Click for copyable input
The drinks each person should have, if no two person is to have the same drink:
Click for copyable input