On fans in multigraphs

We introduce a unifying framework for studying edge‐coloring problems on multigraphs. This is defined in terms of a rooted directed multigraph $\cal F$ , which is naturally associated to the set of fans based at a given vertex u in a multigraph G . We call $\cal F$ the “Fan Digraph.” We show that fans in G based at u are in one‐to‐one correspondence with directed trails in $\cal F$ starting at the root of $\cal F$ . We state and prove a central theorem about the fan digraph, which embodies many edge‐coloring results and expresses them at a higher level of abstraction. Using this result, we derive short proofs of classical theorems. We conclude with a new, generalized version of Vizing's Adjacency Lemma for multigraphs, which is stronger than all those known to the author. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 301–318, 2006