MathCastle
Graph TheoryHardDirected Graphs and Network Flows

Directed Graphs and Network Flows · Hard problem

Five teams 1,…,51,\dots,5 play a round robin with results 1→21\to2, 1→31\to3, 1→41\to4, 5→15\to1, 2→32\to3, 4→24\to2, 2→52\to5, 3→43\to4, 3→53\to5, 4→54\to5 (arrows point from winner to loser). What is the minimum number of games whose outcome would have to be reversed to make the results transitive (some ordering of the teams where every team beats every team ranked below it)?