Complete DAGs

[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 , 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