# Colouring the graph

We have a directed simple graph $G$. Out-degree of any vertex is at most $k$ in $G$. We need to show that $G$ is $2k+1$-partite.

• We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. – Raphael Dec 19 '17 at 6:53

Attempt it by induction. Assume the property is true for every graph with less than $n$ vertices. Now let $G$ be a graph with $n$ vertices. Take the vertex $v$, with the smallest in-degree.
How big can the in-degree of this smallest $v$ be? And you know the outdegree of $v$ is at most $k$. So how many vertices is it adjacenct to? Now $G$ minus $v$ is a graph of $n-1$ vertices and so it is coloured with your $2k+1$ colours. Now adding that $v$ back.... (you can finish from here)