MathCastle
Graph TheorySuperchallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Superchallenge problem

A digraph has vertices 1,…,61,\dots,6 with arcs 1→21\to2, 2→12\to1 (a 22-cycle), 5→65\to6, 6→56\to5 (another 22-cycle), and also 2→32\to3, 1→41\to4, 2→52\to5. What is the minimum number of new arcs that must be added so the digraph becomes strongly connected?