MathCastle
Graph TheoryChallengeGraph Algorithms

Graph Algorithms · Challenge problem

A directed graph on vertices 11–66 has edges 1→2,2→3,3→1,3→4,4→5,5→3,5→61\to2, 2\to3, 3\to1, 3\to4, 4\to5, 5\to3, 5\to6. This digraph has directed cycles, so it has no topological order. What is the fewest edges that must be removed so that the remaining digraph IS a DAG?