MathCastle
Graph TheorySuperchallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Superchallenge problem

A digraph has two separate pieces: {1,2,3}\{1,2,3\} with arcs 1→21\to2, 2→32\to3 only (no arc 3→13\to1), and {4,5,6}\{4,5,6\} with arcs 4→54\to5, 5→65\to6 only (no arc 6→46\to4) – no arcs at all between the two pieces. What is the minimum number of new arcs that must be added so the whole digraph has an Eulerian circuit?