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.

  • 1
    $\begingroup$ 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. $\endgroup$ – 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)

  • $\begingroup$ Please consider not to encourage undesirable posting behaviour. $\endgroup$ – Raphael Dec 19 '17 at 6:53
  • $\begingroup$ @Raphael When I posted this answer, the original post did the things you suggest in the original post's comment: the question asker stated that a greedy method was attempted and a proof by contradiction via a minimal counterexample was attempted. I don't think it was out of line to suggest an induction approach. $\endgroup$ – JimN Dec 19 '17 at 7:16
  • $\begingroup$ @Raphael Maybe you should just roll back my edits. Clearly my ideas were upto no good. $\endgroup$ – User Not Found Dec 19 '17 at 9:32
  • $\begingroup$ @JimN Never mind then, I didn't check the history. $\endgroup$ – Raphael Dec 19 '17 at 10:22
  • $\begingroup$ @UserNotFound I'll leave the editing to you. $\endgroup$ – Raphael Dec 19 '17 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.