Sufficient condition for $k$-colorability We know that a graph is $ 2 $-colorable iff it has no odd cycles. I am asked to generalize this statement to the following: a graph is $ k $-colorable if each vertex is in less than $ \binom{k}{2} $ distinct odd cycles.
I am having trouble with this proof: let's prove by induction on the size of the vertex set of $ G $. Clearly it is true if $ |V(G)| \leq k $. Suppose it is true for $ |V(G)| < n $, and let $ G' = G - \{ x \} $. Since removing a vertex does not create more cycles, we have that $ G' $ is $ k $-colorable. Now we have to show that we can color $ x $ without creating a conflict. But how to proceed? Help is greatly appreciated.
 A: The idea in the last step you're having trouble with is essentially the same as the idea of "Kempe chains" in the proof of the five-color theorem.
If we're adding the vertex $x$ back in, and its neighbors don't already use all $k$ colors, then it's easy to color $x$: just give it a color that's not used by its neighbors.
If all $k$ colors are used on the neighbors of $x$, we may try the following algorithm:


*

*Let Azure and Beige be any two of the colors.

*Let $G_{AB}$ be the graph obtained by the following process:


*

*Start with all neighbors of $x$ which are colored Azure.

*Next, add on all neighbors of those vertices which are colored Beige.

*Next, add on all neighbors of those vertices which are colored Azure.

*Keep going until there are no more vertices to add.


*Reverse the colors of $G_{AB}$: switch Azure to Beige and Beige to Azure.

*Color $x$ Azure.


If all goes well, then in the new coloring, $x$ no longer has any neighbors colored Azure, all of them have been switched to Beige. So we are free to color $x$ Azure, and get a $k$-coloring of $G$.
The trouble is that $G_{AB}$ could eventually include some neighbors of $x$ which are colored Beige. If it does, then reversing the colors of $G_{AB}$ gets rid of all neighbors of $x$ colored Azure (turning them into Beige), but turns some of $x$'s Beige neighbors into Azure, so $x$ still has Azure neighbors, and there's no way to color $x$.
However, if that happens, then there is an Azure-Beige odd cycle containing $x$: a cycle that starts at $x$ and goes through $G_{AB}$, alternating Azure-Beige-Azure-Beige-...-Azure-Beige until it comes back to $x$.
By assumption, there are fewer than $\binom k2$ odd cycles through $x$. Well, there are $\binom k2$ pairs of colors we could have used in place of Azure and Beige. Therefore, there is a pair of colors that does not result in such a cycle, and our recoloring algorithm will work for that pair of colors.
