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.


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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.