HOME

A trifle

Show original manuscript

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 &#x2265 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 &#x2264 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 5
5671 AL NUENEN
The Netherlands		 prof.dr.Edsger W.Dijkstra
Burroughs Research Fellow
transcribed by Xiaozhou (Steve) Li
Mon, 12 Oct 2009