  For a multigraph $G$, $\chi'(G)$ denotes the chromatic index of $G$,
$\Delta(G)$ the maximum degree of $G$, and $\Gamma(G) = \max\left\{\left\lceil
\frac{2|E(H)|}{|V(H)|-1} \right\rceil: H \subseteq G \text{ and } |V(H)| \text{
odd}\right\}$. As a generalization of Vizing's classical coloring result for
simple graphs, the Goldberg-Seymour conjecture, posed in the 1970s, states that
$\chi'(G)=\max\{\Delta(G), \Gamma(G)\}$ or $\chi'(G)=\max\{\Delta(G) + 1,
\Gamma(G)\}$. Hochbaum, Nishizeki, and Shmoys further conjectured in 1986 that
such a coloring can be found in polynomial time. A long proof of the
Goldberg-Seymour conjecture was announced in 2019 by Chen, Jing, and Zang, and
one case in that proof was eliminated recently by Jing (but the proof is still
long); and neither proof has been verified. In this paper, we give a proof of
the Goldberg-Seymour conjecture that is significantly shorter and confirm the
Hochbaum-Nishizeki-Shmoys conjecture by providing an $O(|V|^5|E|^3)$ time
algorithm for finding a $\max\{\Delta(G) + 1, \Gamma(G)\}$-edge-coloring of
$G$.
