MathCastle
Graph TheoryChallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Challenge problem

A digraph has two separate pieces: {1,2,3}\{1,2,3\} with arcs 1→21\to2, 2→32\to3, 3→13\to1, and {4,5,6}\{4,5,6\} with arcs 4→54\to5, 5→65\to6, 6→46\to4 (no arcs at all between the two pieces, and every vertex already has equal in-degree and out-degree within its own piece). What is the minimum number of new arcs that must be added so the whole digraph has an Eulerian circuit?