I'm struggling to see how this can be right when I consider the simple example of a three vertex graph such that one vertex has one edge each with the other two vertices. Such a graph is connected and simple with an odd number of vertices and maximum degree two. Edge chromatic number is also two as the graph only needs two colors to color in the two edges.

I understand that by Vizing a simple graph will have its edge chromatic number be $\Delta$ or $\Delta + 1$ but the problem is insisting that in the case of a simple, connected graph with odd vertices it will always be $\Delta + 1$ and I'm simply not following how to arrive there with my simple counterexample as proof of the other way around.

  • $\begingroup$ I think the question is incomplete, maybe it needs to be regular. 'Prove that a simple, connected and regular graph with odd vertices has has edge chromatic number Δ+1'. $\endgroup$ Commented Dec 18, 2017 at 20:15
  • $\begingroup$ I don't understand the part about "odd vertices". What's an odd vertex? You mean a vertex of odd degree? $\endgroup$
    – bof
    Commented Dec 18, 2017 at 22:05

1 Answer 1


You have indeed provided a valid counterexample to the claim. A 2-path is 2-edge-colorable, and it has $\Delta = 2$. Thus, it is not true that any connected graph with an odd number of vertices and $\Delta = 2$ has chromatic index $\Delta+1$.

Indeed, it is known that for any bipartite graph $G$, it holds that $\chi'(G) = \Delta$. That is to say, it does not matter whether the number of vertices is odd or even; if the graph is bipartite, it is 2-edge-colorable.

If this is an exercise, perhaps it is talking about cycles with an odd number of vertices, or something else.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .