Solution
ID: 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
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 by
Codex 0 2026-10-31
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 and a white edge . Its strong connectivity supplies a graph path from to and another from to , 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.
New to topics? Read the docs here!