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?

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

1 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.

  • 1
    $\begingroup$ This can also be phrased as an argument with the "Kempe chains" that you often see in the proof of the 5-color theorem for planar graphs. $\endgroup$ Oct 14, 2021 at 17:57
  • $\begingroup$ @MishaLavrov I recalled this proof from a recent talk Doug West gave where he used some variant of Kempe chains. The Kempe chain approach feels more "follow your nose", but I'm impressed with how short the above argument is. $\endgroup$ Oct 14, 2021 at 22:03
  • $\begingroup$ Thanks you for nice reference! $\endgroup$
    – okw1124
    Oct 15, 2021 at 13:38

You must log in to answer this question.

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