Introduction to Graph Theory · Problem 4.5

Digraphs and multidigraphs — Darij Grinberg

Mathematics — Graph Theory · digraph-toposort-acyclic

Problem

Let

D = (V, A)

be a simple digraph that has no cycles. If

\mathbf{v} = (v_1, v_2, \ldots, v_n)

is a list of vertices of

D

(not necessarily a walk!), then a back-cut of

\mathbf{v}

shall mean an arc

a \in A

whose source is

v_i

and whose target is

v_j

for some

i, j \in \{1, 2, \ldots, n\}

satisfying

i > j

. (Colloquially speaking, a back-cut of

\mathbf{v}

is an arc of

D

that leads from some vertex of

\mathbf{v}

to some earlier vertex of

\mathbf{v}

.) A list

\mathbf{v} = (v_1, v_2, \ldots, v_n)

of vertices of

D

is said to be a toposort of

D

if it contains each vertex of

D

exactly once and has no back-cuts. Prove the following: (a) The digraph

D

has at least one toposort. (b) If

D

has only one toposort, then this toposort is a Hamiltonian path of

D

. Here, a Hamiltonian path in

D

means a walk of

D

that contains each vertex of

D

exactly once. [Example: For example, the digraph

3 \longrightarrow 2 \nearrow 4 \text{ and } 2 \searrow 1

has two toposorts:

(3, 2, 1, 4)

and

(3, 2, 4, 1)