Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 8 / c / Solution

Here the source's unrestricted “cycle” means a closed walk, permitting repeated vertices; part (d) explicitly separates this from a simple cycle.^[ref]

Suppose a closed walk contains both colours. Any two vertices on it reach one another by following suitable portions of the closed walk. All its vertices, and therefore all its edges, lie inside one strongly connected component. That strongly connected component contains internal edges of both colours.

Conversely, suppose one strongly connected component contains a black edge $u\to v$ and a white edge $x\to y$. Its strong connectivity supplies a graph path from $v$ to $x$ and another from $y$ to $u$, both inside the component. ConcatenateThis is a closed walk containing both chosen edges. Either connecting graph path may have length zero. Thus the mixed-colour closed walk criterion isThe edges must be internal: differently coloured edges merely leaving a strongly connected component do not establish the claim.