Reference no: EM131576307

Question: Show that if G is a chromatically k-critical graph, then the degree of every vertex of G is at least k - 1.

A k-tuple coloring of a graph G is an assignment of a set of k different colors to each of the vertices of G such that no two adjacent vertices are assigned a common color. We denote by χk(G) the smallest positive integer n such that G has a k-tuple coloring using n colors. For example, χ2(C4) = 4. To see this, note that using only four colors we can assign two colors to each vertex of C4, as illustrated, so that no two adjacent vertices are assigned the same color. Furthermore, no fewer than four colors suffice because the vertices v1 and v2 each must be assigned two colors, and a common color cannot be assigned to both v1 and v2. (For more information about k-tuple coloring, see [MiRo91].)