Let G be a connected Graph find all graphs that satisfy $\chi(G) > \chi'(G)$

Question

this was my exam question today on Graph theory couldn't figure much about it, looking forward to your help.

Let G be a connected Graph find all graphs that satisfy $\chi(G) > \chi'(G)$

Answer 1

This question has been asked a few time on mathoverflow and is answered in the comments of Finding all graphs with chromatic number greater than chromatic index.. I am merely gathering the comments of this thread as an answer.

First, Vizing's theorem (c.f. https://en.wikipedia.org/wiki/Edge_coloring#Vizing's_theorem) that for any graph, the edge chromatic number $\chi'(G)$ is either $\Delta(G)$ or $\Delta(G) + 1$, where $\Delta(G)$ is the maximum degree of your graph $G$.

On the other hand Brooks' theorem (https://en.wikipedia.org/wiki/Brooks%27_theorem) states that $ \chi(G) ≤ \Delta (G)$ for a connected G, unless G is a complete graph or an odd cycle, so the two families that need to be checked are complete graphs and odd cycles.

For odd cycles $\chi(G) = \chi'(G) = \Delta(G)+1 = 3$, so we can forget about them

For complete graphs $\chi(K_n)=n $ we have to distinguish between odd and even: $\chi'(K_{2n})=2n-1$ while $\chi'(K_{2n-1}) = 2n-1$, we can conclude.