HOME

Complete DAGs

Show original manuscript

[DAG is just another TLA I don't approve of; it stands for "Directed Acyclic Graph .]

In a recent manuscript —in the literal sense of the word— : "Some properties of the relative converse" (March 1995), Tony Hoare plays with tetrahedra of which the edges may be directed. (As by-product of his considerations he finds, for instance, that "any non-cyclic ascription of directions to any five of the edges can be non-cyclically extended to the sixth edge.") Here is a little bit of related theory.

*                *
*

Let K be the complete graph with n vertices, in which each edge has a direction. Then the following 3 statements are equivalent

(i)    K contains no cyclic paths

(ii)   K contains no cyclic paths of length 3

(iii)  the outdegrees of the vertices of K are the values 0 through n-1

The equivalences hold for n=1, since for n=1, (i), (ii), and (iii) are all true. For general n, the proof proceeds by mathematical induction. The induction step itself is done by cyclic implication: we now consider the complete (n+1)-graph K' with directed edges, and observe for it

(i) ⇒ (ii)

This follows —independently of the induction hypothesis— from the fact that "of length 3" is a restriction.

(ii) ⇒ (iii)

Let A be of K' a vertex of maximum outdegree; let K be the n-graph that remains after removal of A and its n connecting edges. Because of (ii), also K contains no cycles of length 3 and, ex hypothese, the outdegrees of its vertices are the values 0 through n-1; consequently we are done when we show that A has outdegree n (note that then the vertices of K have the same outdegree in K as in K').

Let B be the vertex with outdegree n-1 in K; since, by construction, A is not a vertex of K, A and B are different vertices. We now first deal with
the edge AB, and then with the remaining edges connecting A to K.

The direction of edge AB is AB for the assumption BA   leads to a contradiction: then B would have in K' the (maximum) outdegree n, and so would A (by virtue of how it has been chosen: outdegree A ≥ outdegree B), but in the directed complete (n+1)-graph, at most 1 vertex has the maximum outdegree n.

Let C be a third vertex; then, because C is a vertex of K, in which B has the maximal outdegree n-1, the direction of edge BC is B→C. From AB, BC, and the absence of cycles of length 3 in K', we conclude that the direction of AC is AC. (Note that, so far, we had only used the absence of cycles in K.) Hence, A has outgoing edges only, quod erat demonstrandum.

(iii) ⇒ (i)

Assume (iii) for K'; let A be the vertex of maximum outdegree n; let K be the n-graph that remains after removal of A and its n connecting edges. Possible cyclic paths in K' are then of two kinds, either they include A, or they lie in K.

Because A has outgoing edges only, no cyclic path leads through it; because of assumption (iii) for K' and of the fact that A has outgoing edges only, we conclude (iii) for K and, ex hypothese, that no cyclic paths lie in K. So, K' contains no cyclic paths, quod erat demonstrandum.

*                *
*

The absence of cyclic paths in the complete graph tells us —with apologies for the picture!— that each triangle is of the form triangle with directed arcs AB, BC, and AC , i.e. → is a transitive relation. Hiding this fact so far could be considered a conscious obfuscation on my part.

prof. dr. Edsger W. Dijkstra
Department of Computer Sciences
The University of Texas at Austin
Austin, TX 78712-1188
USA