[2][3] The Dinitz theorem is that given an n × n square array, a set of m symbols with m ≥ n, and for each cell of the array an n-element set drawn from the pool of m symbols, it is possible to choose a way of labeling each cell with one of those elements in such a way that no row or column repeats a symbol.
That is, if each edge of the complete bipartite graph is assigned a set of
Galvin's proof generalizes to the statement that, for every bipartite multigraph, the list chromatic index equals its chromatic index.
The more general edge list coloring conjecture states that the same holds not only for bipartite graphs, but also for any loopless multigraph.
[4] The Dinitz theorem is also related to Rota's basis conjecture.