  Let $\Delta(G)$ and $\chi'(G)$ be the maximum degree and chromatic index of a
graph $G$, respectively.
  Appearing in different format, Gupta\,(1967), Goldberg\,(1973),
Andersen\,(1977), and Seymour\,(1979) made the following conjecture: Every
multigraph $G$ satisfies $\chi'(G) \le \max\{ \Delta(G) + 1, \Gamma(G) \}$,
where $\Gamma(G) = \max_{H \subseteq G} \left\lceil \frac{ |E(H)| }{ \lfloor
\tfrac{1}{2} |V(H)| \rfloor} \right\rceil$ is the density of $G$. In this
paper, we present a polynomial-time algorithm for coloring any multigraph with
$\max\{ \Delta(G) + 1, \Gamma(G) \}$ many colors, confirming the conjecture
algorithmically. Since $\chi'(G)\geq \max\{ \Delta(G), \Gamma(G) \}$, this
algorithm gives a proper edge coloring that uses at most one more color than
the optimum. As determining the chromatic index of an arbitrary graph is
$NP$-hard, the $\max\{ \Delta(G) + 1, \Gamma(G) \}$ bound is best possible for
efficient proper edge coloring algorithms on general multigraphs, unless
$P=NP$.
