MathCastle
Graph TheoryHardDirected Graphs and Network Flows

Directed Graphs and Network Flows · Hard problem

A digraph has vertices A,B,C,D,EA,B,C,D,E and arcs A→CA\to C, C→DC\to D, D→ED\to E, E→AE\to A, A→DA\to D, B→CB\to C. What is the minimum number of new arcs that must be added so every vertex has equal in-degree and out-degree (as needed for an Eulerian circuit)?