A trifle

EWD688 · 1976–1979 · PDF · source transcription · Source language: English.

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 5
5671 AL NUENEN
The Netherlands

prof.dr.Edsger W.Dijkstra
Burroughs Research Fellow

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