MathCastle
Graph TheoryChallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Challenge problem

A digraph has vertices 1,…,71,\dots,7 with arcs 1→21\to2, 2→32\to3, 3→13\to1 (a 33-cycle), 4→54\to5, 5→45\to4 (a 22-cycle), 6→76\to7, 7→67\to6 (a 22-cycle), and 1→41\to4, 4→64\to6, 1→61\to6. Among all (72)=21\binom{7}{2}=21 pairs of vertices, how many pairs are NOT mutually reachable (there fails to be a directed path in at least one of the two directions)?