4 1.3 Proper Edge Colorings A Sisasetof c rs(and typically S =Zk for som ≥2，wihh property that c(e)≠ c(f)for every two adja chosen from a set of k colors,then c is called a k-edge coloring of G.The minimum positive integer k for which G has a k-edge coloring is called the chromatic index of G and is denoted by x'(G). It is immediate for every nonempty graph G that x'(G)>A(G).The most important theorem dealing with chromatic index is one obtained by the Russian mathematician Vadim Vizing. Theorem 1.3.1 ([741).For every nonempty graph G. X(G≤△(G+1. As a result of Vizing's theorem,the chromatic index of every nonempty graph G is one of two numbers,namely△(Gor△(G)+1.A graph G with x'(G)=△(G is called a class one graph while a graph Gwith x'(G)=A(G)+1 is called a class grapThe chromatic index of complete graphs is given in the following result. Theorem 1.3.2.For each integer n 2. I'(Kn)=n-1 ifn is even n if n is odd. Therefore.K,is a class one graph if n is even and is a class two graph if n is odd. The fact that K is a class one graph if and only if n is even is also a consequence of the following. An immediate consequence of this result is stated next. Corollary 1.3.4.Every regular graph of odd order is a class two graph. The next two results describe classes of graphs that are class one graphs.The first theorem is due to Denes Konig. Theorem 1.3.5 ([48)).Every bipartite graph is a class one graph If a graphGofodd order has sufficiently many edges.then must be a classtw graph.A graph G of order n and size m is called overfull if m> △(G)n/2.fC has even order n,then m A(G)[n/2]and so G is not overfull.On the other hand. a graph of odd order may be overfull. Theorem 1.3.6.Every overfull graph is a class two graph.4 1 Introduction 1.3 Proper Edge Colorings A proper edge coloring c of a nonempty graph G is a function c W E.G/ ! S, where S is a set of colors (and typically S D Œk or S D Zk for some integer k  2), with the property that c.e/ ¤ c.f/ for every two adjacent edges e and f of G. If the colors are chosen from a set of k colors, then c is called a k-edge coloring of G. The minimum positive integer k for which G has a k-edge coloring is called the chromatic index of G and is denoted by 0 .G/. It is immediate for every nonempty graph G that 0 .G/  .G/. The most important theorem dealing with chromatic index is one obtained by the Russian mathematician Vadim Vizing. Theorem 1.3.1 ([74]). For every nonempty graph G, 0 .G/  .G/ C 1: As a result of Vizing’s theorem, the chromatic index of every nonempty graph G is one of two numbers, namely .G/ or .G/ C 1. A graph G with 0 .G/ D .G/ is called a class one graph while a graph G with 0 .G/ D .G/ C 1 is called a class two graph . The chromatic index of complete graphs is given in the following result. Theorem 1.3.2. For each integer n  2, 0 .Kn/ D n 1 if n is even n if n is odd. Therefore, Kn is a class one graph if n is even and is a class two graph if n is odd. The fact that Kn is a class one graph if and only if n is even is also a consequence of the following. Theorem 1.3.3. A regular graph G is a class one graph if and only if G is 1-factorable. An immediate consequence of this result is stated next. Corollary 1.3.4. Every regular graph of odd order is a class two graph. The next two results describe classes of graphs that are class one graphs. The first theorem is due to Denés König. Theorem 1.3.5 ([48]). Every bipartite graph is a class one graph. If a graph G of odd order has sufficiently many edges, then G must be a class two graph. A graph G of order n and size m is called overfull if m > .G/bn=2c. If G has even order n, then m  .G/bn=2c and so G is not overfull. On the other hand, a graph of odd order may be overfull. Theorem 1.3.6. Every overfull graph is a class two graph.