In addition to coloring the vertices of a graph, mathematicians are interested in

Chapter 52, Problem 52.18

(choose chapter or problem)

In addition to coloring the vertices of a graph, mathematicians are interested in coloring the edges. In a vertex coloring, vertices that are on a common edge must be different colors. In an edge coloring, edges that share a common vertex must be different colors. More precisely, a proper k-edge coloring of a graph G is a function f W E.G/ ! f1; 2; : : : ; kg with the property that if e and e 0 are distinct edges that have a common end point, then f .e/ 6D f .e0 /. The edge chromatic number of G, denoted 0 .G/, is the least k such that G has a proper k-edge coloring. Please do: a. Show that the edge chromatic number of the graph in the figure is 4. b. Prove that if T is a tree, then 0 .T / D .T /. c. Give an example of a graph G for which 0 .G/ > .G/.