MathCastle
Graph TheorySuperchallengeDirected Graphs and Network Flows

Directed Graphs and Network Flows · Superchallenge problem

A digraph has two groups: {1,2,3}\{1,2,3\} with arcs 1→21\to2, 2→32\to3, 3→13\to1, and {4,5,6}\{4,5,6\} with arcs 4→54\to5, 5→65\to6, 6→46\to4, plus a single extra arc 3→43\to4 (and NO other arcs between the groups – most pairs across the two groups never play at all, so this is not a complete tournament). Call a vertex a king if it reaches every other vertex within two steps. How many kings does this digraph have?