IBM Ponder This #018 · October 1999

A directed graph has vertices and directed edges. It has no loops and no multiple edges with the same source and destination. A path of length two from $B$ to $C$ consists of edges $(B,D)$ and $(D,C)$ for some intermediate vertex $D$.

The graph has between $30$ and $40$ vertices, inclusive. For every ordered pair of vertices $B,C$, there is either a direct edge $(B,C)$ or exactly one path of length two from $B$ to $C$, but not both. This also applies when $B=C$: there is exactly one path of length two from a vertex to itself.

How many vertices are in the graph?

Solution

Best opened after a real attempt

Solution

To be added.