2
$\begingroup$

A complete graph is an undirected graph in which all pairs of vertices are connected by an edge. A perfect matching is a selection of edges of the graph which touch every vertex exactly once.

Is there a name for a set of perfect matchings of a complete graph that select every edge of the graph exactly once?


Background information for the interested:

One application of a perfect matching of a complete graph is sports scheduling: if vertices are teams, and edges are games between two teams, then the complete graph is a description of all unique pairings that is possible, and a perfect matching is a set of games that includes each team once. If you have T teams, and T/2 fields, then the perfect matching describes games that can be played simultaneously in a single round.

If we want to ensure that each team eventually plays every other team, but no pair of teams play each other twice, we want to find a set of perfect matchings that select all edges of the graph exactly once.

For 8 teams, here are two different sets of perfect matchings that cover the space. The first row happened to be hand-crafted (hence the symmetry) while the second row is the result of round-robin scheduling:

two rows of complete graphs with 8 vertices with various edges visually highlighted

$\endgroup$
3
  • 1
    $\begingroup$ I think it's called a 1-factorization. $\endgroup$ Jan 5, 2020 at 14:27
  • $\begingroup$ @GerryMyerson That certainly seems correct. Thank you! Care to post it as an answer? $\endgroup$
    – Phrogz
    Jan 5, 2020 at 14:41
  • $\begingroup$ Your wish is my command. $\endgroup$ Jan 5, 2020 at 14:44

1 Answer 1

3
$\begingroup$

It's called a 1-factorization. See for example, Wikipedia.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .