= Solution
Here the source's unrestricted “cycle” means a <closed walk>, permitting repeated <vertices>; part (d) explicitly separates this from a <simple cycle>.<Functional programming, design and analysis of algorithms examination paper by the University of Oxford (2013)>[p. 7, Questions 8(c)–(d)]{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. Concatenate
$$
u\xrightarrow{\mathrm{black}}v\leadsto x\xrightarrow{\mathrm{white}}y\leadsto u.
$$
This is a <closed walk> containing both chosen <edges>. Either connecting <graph path> may have length zero. Thus the <mixed-colour closed walk criterion> is
$$
\boxed{\text{a mixed-colour closed walk exists}\iff\text{some SCC has internal edges of both colours}.}
$$
The <edges> must be internal: differently coloured <edges> merely leaving a <strongly connected component> do not establish the claim.
Back to article page
