# Graph with chromatic index 1 billion more than max degree?

For a simple graph, Vizing's Theorem says $\chi '(G)\leq \Delta(G)+1$, where $\chi '(G)$ is the chromatic index (minimum size of an edge coloring) and $\Delta(G)$ is the maximum degree. I want a graph with chromatic index 1 billion more than its highest degree, so obviously we will need some multiple edges.

My idea is to take the complete graph $K_n$ on $n$ vertices, for $n$ very large, and then add multiple edges. Since the degree of $K_n$ is $n-1$ and it has $n(n-1)/2$ edges, it seems that when $n$ is very large we distribute multiple edges around the graph while keeping the degrees relatively small.

## 1 Answer

See this link.

Add an additional $999,999,999$ edges in parallel to each of the $3$ edges of $K_3$, and call this graph $G$. Then you can check $\chi'(G) = 3,000,000,000$ and $\Delta(G) = 2,000,000,000$.

• Ok that works and is a bit simpler than what I was thinking about. Thanks! – Forever Mozart Jun 8 '15 at 22:55