On the existence of rainbows in 1-factorizations of K-2n

Abstract

A 1-factor of a graph G = (V,E) is a collection of disjoint edges which contain all the vertices of V. Given a 2n - 1 edge coloring of K-2n, n greater than or equal to 3, we prove there exists a 1-factor of K-2n whose edges have distinct colors. Such a 1-factor is called a "Rainbow." (C) 1998 John Wiley & Sons, Inc.