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

Question

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?

Answer 1

This was proved by Stong in "Solution to problem 11086" in the American Mathematical Monthly, which you can find at https://www.jstor.org/stable/27641938. I am unable to 'copy-paste' the short argument here, so I give the brief idea.

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.