MathCastle
Graph TheoryHardDirected Graphs and Network Flows

Directed Graphs and Network Flows · Hard problem

A digraph has vertices 1,…,61,\dots,6 and arcs 1→21\to2, 2→12\to1, 3→43\to4, 4→34\to3, 5→65\to6, 6→56\to5, 1→51\to5, 3→53\to5 — three separate 22-cycles, with two of them pointing into the third. What is the minimum number of arcs that must be added to make this digraph strongly connected?