= Solution
Take two directed triangles meeting only at a central <vertex> $a$. Make $a\to b\to c\to a$ entirely black and $a\to d\to e\to a$ entirely white. All five <vertices> lie in one <strongly connected component>, since every <vertex> can reach $a$ and can be reached from $a$. It contains internal <edges> of both colours.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2013/functional-programming-2013-mixed-cycles.png]
{title=Two monochromatic directed triangles sharing one vertex give a mixed closed walk but no mixed simple cycle}
A <closed walk> can traverse the black triangle and then the white triangle. But a <simple cycle> using <edges> from both triangles would have to pass through $a$ to change triangles and pass through $a$ again to return. It would repeat $a$ other than the single start/end identification, contradicting simplicity. Removing $a$ separates the two triangles, so no other transition between them is possible. Therefore
$$
\boxed{\text{one SCC can have both edge colours while every simple cycle is monochromatic}.}
$$
This example avoids <self-loops> and works even when a directed <simple cycle> is required to have at least three <vertices>.
Back to article page
