MathCastle
Graph TheoryMediumDirected Graphs and Network Flows

Directed Graphs and Network Flows · Medium problem

A digraph has vertices 1,…,61,\dots,6 and arcs 1→21\to2, 2→32\to3, 3→13\to1, 3→43\to4, 4→54\to5, 5→45\to4, 5→65\to6. Out of all (62)=15\binom{6}{2}=15 pairs of vertices, how many pairs are NOT mutually reachable?