CSDS 455: Applied Graph Theory
Problem 1: In edge coloring, we assign colors to the edges of G so that all the edges incident to a vertex
receive different colors. χ
(G) is the minimum number of colors required to edge color G.
(G) > ∆(G)+ 1 but for any edge xy, χ
(G−xy) = ∆+ 1. Prove that in every proper edge coloring
of G − xy there exists a path from x to y in which the edges alternate between two colors.
(We can use this fact to prove Vizing’s Theorem: χ
(G) ≤ ∆(G) + 1 by induction.)
Problem 2: Assume G is a ∆-regular multigraph, and assume ∆ is even. Prove that χ