G. Let and D. , Assume that some terminal component, Q , in D is a k-regular tournament

?. As, this implies that Q is also a terminal component in D, a contradiction Therefore no terminal component in D is a k-regular tournament and by induction there is a k-all-out-degreereducing 2k-partition of D . Now add w to a different part to all of its at most 2k ? 1 neighbours in G. This gives a k-all-out-degree-reducing 2k-partition of D

. Moreover, the graph G is not an odd cycle. Therefore, by Brook's Theorem, G admits a proper 2k-colouring. This 2k-colouring gives us the desired k-all-out-degree-reducing 2k-partition of D

J. Bang-jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, 2009.

J. Bang-jensen and F. Havet, Finding good 2-partitions of digraphs I. Hereditary properties, Theoretical Computer Science, vol.636, pp.85-94, 2016.
DOI : 10.1016/j.tcs.2016.05.029

URL : https://hal.archives-ouvertes.fr/hal-01327015

R. Cowen, Some connections between set theory and computer science, Proceedings Lecture Notes in Computer Science, vol.713, pp.14-22, 1993.
DOI : 10.1007/BFb0022548

S. Kreutzer, S. Oum, P. Seymour, D. Van-der-zypen, and D. R. Wood, Majority colourings of digraphs, Electronic J. Combinatorics, vol.24, 2017.

N. Robertson, P. D. Seymour, and R. Thomas, Permanents, Pfaffian Orientations, and Even Directed Circuits, The Annals of Mathematics, vol.150, issue.3, pp.929-975, 1999.
DOI : 10.2307/121059

URL : http://arxiv.org/pdf/math/9911268

T. J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing , STOC '78, pp.216-226, 1978.
DOI : 10.1145/800133.804350

P. D. Seymour, ON THE TWO-COLOURING OF HYPERGRAPHS, The Quarterly Journal of Mathematics, vol.25, issue.1, pp.303-311, 1974.
DOI : 10.1093/qmath/25.1.303

C. Thomassen, Even Cycles in Directed Graphs, European Journal of Combinatorics, vol.6, issue.1, pp.85-89, 1985.
DOI : 10.1016/S0195-6698(85)80025-1

C. Thomassen, The even cycle problem for directed graphs, Journal of the American Mathematical Society, vol.5, issue.2, pp.217-229, 1992.
DOI : 10.1090/S0894-0347-1992-1135027-1