Grinberg-Introduction-Graph-Theory · Problem 4.3

Digraphs and multidigraphs

Mathematics — Graph Theory · digraph-root-common-ancestor

Problem

Let

D = (V, A, \psi)

be a multidigraph. For two vertices

u

and

v

D

, we shall write

u \xrightarrow{*} v

if there exists a path from

u

v

. A root of

D

means a vertex

u \in V

such that each vertex

v \in V

satisfies

u \xrightarrow{*} v

. A common ancestor of two vertices

u

and

v

means a vertex

w \in V

such that

w \xrightarrow{*} u

and

w \xrightarrow{*} v

. Assume that

D

has at least one vertex. Prove that

D

has a root if and only if every two vertices in

D

have a common ancestor.