Chapter 23, PROBLEM SET 23.8 #26

Do you need an answer to a question different from the above? Ask your question!

The edge chromatic number Χ_{e}(G) of a graph G is the minimum number of colors needed for coloring the edges of G so that incident edges get different colors. Clearly, Χ_{e}(G) ≥ max d(u), where d(u) is the degree of vertex u. If G = (S, T; E) is bipartite, the equality sign holds. Prove this for K_{n,n} the complete bipartite graph G = (S, T, E) with S and T consisting of n vertices each.

PROBLEM SET 23.2:

PROBLEM SET 23.4:

PROBLEM SET 23.5:

PROBLEM SET 23.6:

PROBLEM SET 23.7:

PROBLEM SET 23.8: