Graph factorization
In Graph theory, a 1-factor of a graph is a collection of disjoint edges (this is also known as a 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. A Graph G is said to be 1-Factorable if it admits a 1-Facorization.
Example: Draw 7 vertices distributed evenly around a circle, and one in the middle (a total of 8 vertices). Join the middle point to any single point on the circle--call this line L. Join points two 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 8 vertices. Now rotate the lines one vertex to the right (i.e., start over again with the 8 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 8 points.
Each of these perfect matchings can also be looked at as a 1-Factor of the complete graph on 8 vertices. Continuing the process above, you will form a 1-Factorization of the complete graph on 8 vertices. This is a proof that there exists a 1-Factorization of for all n.
