MathCastle
Graph TheoryChallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Challenge problem

A digraph has vertices 1,…,81,\dots,8 with arcs 1→21\to2, 2→32\to3, 3→43\to4, 4→14\to1 (a 44-cycle), 5→65\to6, 6→76\to7, 7→57\to5 (a 33-cycle), and also 4→54\to5, 5→15\to1, 7→87\to8. What is the size of the largest strongly connected component?