1-factorable

From Wikipedia, the free encyclopedia

In graph theory, a 1-factor of a graph is a collection of disjoint edges, which together are incident on all the vertices of the graph (a perfect matching). A 1-factorization of a graph G is a collection of 1-factors such that every edge of G is in exactly one of these 1-factors. The graph is thus "factored" into edge-disjoint subgraphs; in each subgraph, each vertex is the endpoint of exactly one edge. Analogously, an n-factorization factors the graph into disjoint subgraphs in which each vertex is the endpoint of n edges.

A graph G is said to be 1-factorable if it admits a 1-factorization.

[edit] Example

An easy to generate 1-factorization of K₈. Each set of edges with the same color is a 1-factor. (The black lines depict the original circle and are not part of a factorization.)

Draw seven vertices distributed evenly around a circle, and one in the middle, for a total of eight vertices. Join the middle point to any single point on the circle; call this line L. Join points to other points on the circle together if and only if they can be joined together with a line orthogonal to L. Since the points were arranged evenly, this will produce a matching (in fact a perfect matching) of these eight vertices.

Now rotate the lines one vertex to the right: Start over again with the eight vertices as described and join the center point to the point in the circle directly clockwise from the first one chosen. Join the other points on the circle in a similar matter as before. This is again another perfect matching of these eight points.

Each of these perfect matchings can also be looked at as a 1-factor of the complete graph on eight vertices, K₈. Continuing the process above, you will form a 1-factorization of K₈. This is a proof that there exists a 1-factorization of K_2n for all n.

A 1-factorization of a complete graph corresponds to pairings in a round-robin tournament.