# If every vertex of $G$ lies in fewer than ${k \choose 2}$ odd cycles, then $G$ is $k$-colorable

I have a brief idea for the proof:
Since the chromatic number of an odd cycle is $$3$$, if a vertex $$v$$ is colored $$c_1$$, an odd cycle containing $$v$$ should be colored with at least $$3$$ colors $$c_1$$, $$c_2$$ and $$c_3$$.
If $$v$$ is contained in $$\leq {k-1 \choose 2}$$ cycles, we can choose $$2$$ other colors for each odd cycle.
But this idea is too brief - I did not consider odd cycles having more than $$2$$ common vertices.
Also, I have no idea with why the boundary is $$<{k \choose 2}$$, not $$\leq { k-1 \choose 2}$$.
Can you help me?

• What is the source of this problem?
– bof
Oct 12, 2021 at 4:34

The $$\binom{k}{2}$$ is probably not sharp, so we instead should use it as a hint for the proof that we need to consider pairs of colors. The key idea is that for any two colors in a proper coloring, the vertices colored with those two colors induce a bipartite graph, and so we may 'swap' the two colors on any component of this induced graph.
Suppose we have $$k$$-colored the graph apart from a vertex $$v$$. For every two colors, either the graph induced on these two colors and $$v$$ is bipartite, in which case we can recolor in order to color $$v$$, or this induced graph has an odd cycle containing $$v$$. Since $$v$$ is in fewer than $$\binom{k}{2}$$ odd cycles, the first case must occur as desired.