= Solution
The <edge chromatic number> $\chi'(G)$ is the least number of colors in a proper coloring of edges, where incident edges receive distinct colors. <Hall marriage theorem> says a bipartite graph has a matching saturating one side exactly when $|N(S)|\geq|S|$ for every subset $S$ of that side.
In a 4-regular bipartite graph, the $4|S|$ edges leaving $S$ all enter $N(S)$, whose vertices can receive at most $4|N(S)|$ such edges. Hence Hall's condition holds and there is a perfect matching. Remove it and repeat in the resulting 3-, 2-, and 1-regular bipartite graphs. The four perfect matchings give a four-edge-coloring, while every vertex requires four distinct colors. Therefore
$$
\boxed{\chi'(G)=4}.
$$
Back to article page
