# A trifle.

In EWD687, Scholten and I used without proof the (rather obvious)

Theorem. In a directed, finite graph, such that
a) any node with an incoming edge has outgoing edges, and
b) no node has more than one incoming edge,
the edges form only directed cyclic paths.

I gave myself the task to find a proof as nice as the theorem is obvious. The following one I really like.

Proof.

Let for each node IN be the number of its incoming edges and OUT the number of its outgoing edges. Then a) states that for each node we have

 IN = 0 or OUT ≥ 1      ; (1)
and b) states that for each node we have
 IN = 0 or IN = 1       . (2)
From (1) and (2) we conclude that for each node we have
 IN ≤ OUT      . (3)
Because each edge is incoming edge and outgoing edge we have, summed over the whole graph
 the sum of the IN's = the sum of the OUT's      . (4)
From (3) and (4) we conclude that for each edge we have
 IN = OUT (5)
which in combination with (2) gives that we have for each node
 (IN = OUT = 0) or (IN = OUT = 1)      , (6)
a conclusion that is equivalent with the statement that the edges form only directed cyclic paths. (End of proof.)

27th of October 1978

 Plataanstraat 55671 AL NUENEN The Netherlands prof.dr.Edsger W.Dijkstra Burroughs Research Fellow

transcribed by Xiaozhou (Steve) Li
Mon, 12 Oct 2009