MathCastle
Graph TheoryHardDirected Graphs and Network Flows

Directed Graphs and Network Flows · Hard problem

A 55-team tournament has results 1→21\to2, 2→32\to3, 3→13\to1, 1→41\to4, 4→24\to2, 3→43\to4, 1→51\to5, 5→25\to2, 5→35\to3, 4→54\to5. What is the smallest number of individual games whose winner and loser would need to be swapped so that the results become transitive (admit a ranking of the 55 teams with every game won by the higher-ranked team)?