On a finite directed graph in which every vertex is moved

Received: not recorded. Accepted: not recorded.

1. Setting

Let D = (V, E) be a finite directed graph. Read an edge u → v as “u moves v”. Suppose

∀v ∈ V.  ∃u ∈ V.  u → v,

that is, every vertex is moved by some vertex. Call such a graph unsourced.

2. Lemma

Every unsourced finite graph contains a cycle.

Choose any v₀ ∈ V. By hypothesis there is v₁ with v₁ → v₀, and v₂ with v₂ → v₁, and so on. Since V is finite, the sequence v₀, v₁, v₂, … must repeat a vertex. The segment between the two occurrences is a cycle.

3. The instance under study

Consider the graph on four vertices

V = { puppet, master, stage, audience }

with the edges reported in the source: the master moves the puppet; the puppet moves the master; the stage moves and is moved; the audience moves and is moved. Each vertex has in-degree at least one. The graph is unsourced, and by §2 contains a cycle. There is no first mover in V.

4. Remark on the index

We note, without offering an interpretation, that V as given is incomplete. The graph is stated in a document; the document is read; and the reading is an act which moves the vertices in V — it is by being read that the puppet is caused to dance again.¹ A vertex therefore exists which is not listed in V, whose in-degree we have not established and cannot establish from inside the document.²

The archive records this vertex under the second-person singular pronoun, in Italian, since that is the language of the room to which this paper is a corridor.

---

¹ Any reader who has reached this footnote has already performed the operation and may verify it directly.

² Whether the fifth vertex is itself moved is, from within V, undecidable. It is not undecidable from where the fifth vertex is sitting.

back to the surface