Directed graph with no cycles
Source: 2012 Baltic Way, Problem 8
November 22, 2012
combinatorics unsolvedcombinatorics
Problem Statement
A directed graph does not contain directed cycles. The number of edges in any directed path does not exceed 99. Prove that it is possible to colour the edges of the graph in 2 colours so that the number of edges in any single-coloured directed path in the graph will not exceed 9.