__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 `A`→`B` for the assumption `B`→`A` 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 `A`→`B`, `B`→`C`, and the absence of cycles of length 3 in `K'`, we conclude that the direction of `AC` is `A`→`C`. (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