# Is it true that if a graph is bipartite iff it is class 1 (edge-coloring)?

A graph is class 1 if its edge set can be colored with $\Delta(G)$ colors, where $\Delta(G)$ is the maximum degree over all vertices in G. A graph is class 2 if we need $\Delta(G)+1$ colors to color the edge set. I think that if a graph is bipartite then we can color its edges with $\Delta(G)$ colors, while when it is not bipartite this cannot be done.

Is there any counterexample for this? Or is it true?

• This question would be greatly improved by defining “class 1” and $\Delta(G)$ – Stella Biderman Jan 14 '18 at 12:42
• @StellaBiderman done – mandella Jan 14 '18 at 12:57
• Do you use the definition of coloring where a graph is $m$-colorable if there is a way to assign $m$ colors legally, or do you also require that $m$ be minimal. That’s is, would you say that $C_6$ is both $2$ colorable and $6$ colorable, or just $2$ colorable? – Stella Biderman Jan 14 '18 at 13:05
• @StellaBiderman no I want the least $m$. So $C_6$ would be 2-colorable. – mandella Jan 14 '18 at 13:07
• Take the complete 4 graph. Remove an edge. This has maximum degree 3, it is 3 colorable, but is not bipartite – Exodd Jan 14 '18 at 13:57

It is a theorem of König that all bipartite graphs $G$ are $\Delta(G)$-edge-colorable. See this math stackexchange thread Edge-coloring of bipartite graphs.

It is not true that all $\Delta(G)$-edge-colorable graphs are bipartite. Take $K_4$, which is not bipartite but is $3$-edge-colorable.

• Yes! Thank you. I could not find a counterexample :) – mandella Jan 15 '18 at 9:01