Editing Edge coloring (section)

==Examples==
A [[cycle graph]] may have its edges colored with two colors if the length of the cycle is even: simply alternate the two colors around the cycle. However, if the length is odd, three colors are needed.<ref>{{harvtxt|Soifer|2008}}, problem 16.4, p. 133.</ref>

[[File:Complete-edge-coloring.svg|thumb|Geometric construction of a 7-edge-coloring of the [[complete graph]] {{math|''K''<sub>8</sub>}}. Each of the seven color classes has one edge from the center to a polygon vertex, and three edges perpendicular to it.]]
A [[complete graph]] {{mvar|K<sub>n</sub>}} with {{mvar|n}} vertices is edge-colorable with {{math|''n'' &minus; 1}} colors when {{mvar|n}} is an even number; this is a special case of [[Baranyai's theorem]]. {{harvtxt|Soifer|2008}} provides the following geometric construction of a coloring in this case: place {{mvar|n}} points at the vertices and center of a regular {{math|(''n'' &minus; 1)}}-sided polygon. For each color class, include one edge from the center to one of the polygon vertices, and all of the perpendicular edges connecting pairs of polygon vertices. However, when {{mvar|n}} is odd, {{mvar|n}} colors are needed: each color can only be used for {{math|(''n'' &minus; 1)/2}} edges, a {{math|1/''n''}} fraction of the total.<ref>{{harvtxt|Soifer|2008}}, problem 16.5, p. 133. The fact that either {{mvar|n}} or {{math|(''n'' &minus; 1)}} colors are needed is an instance of [[Vizing's theorem]].</ref>

Several authors have studied edge colorings of the [[odd graph]]s, {{mvar|n}}-regular graphs in which the vertices represent teams of {{math|''n'' &minus; 1}} players selected from a pool of {{mvar|2''n'' − 1}} players, and in which the edges represent possible pairings of these teams (with one player left as "odd man out" to referee the game). The case that {{math|1=''n'' = 3}} gives the well-known [[Petersen graph]]. As {{harvtxt|Biggs|1972}} explains the problem (for {{math|1=''n'' = 6}}), the players wish to find a schedule for these pairings such that each team plays each of its six games on different days of the week, with Sundays off for all teams; that is, formalizing the problem mathematically, they wish to find a 6-edge-coloring of the 6-regular odd graph {{math|''O''<sub>6</sub>}}. When {{mvar|n}} is 3, 4, or 8, an edge coloring of {{math|''O''<sub>''n''</sub>}} requires {{math|''n'' + 1}} colors, but when it is 5, 6, or 7, only {{mvar|n}} colors are needed.<ref>{{harvtxt|Biggs|1972}}; {{harvtxt| Meredith|Lloyd|1973}}; {{harvtxt|Biggs|1979}}.</ref>