Introduction to Graph Theory · Problem 4.3

Digraphs and multidigraphs — Darij Grinberg

Mathematics — Graph Theory · digraph-roots-common-ancestors

Problem

Let D=(V,A,ψ)D = (V, A, \psi) be a multidigraph. For two vertices uu and vv of DD, we shall write u→∗vu \xrightarrow{*} v if there exists a path from uu to vv. A root of DD means a vertex u∈Vu \in V such that each vertex v∈Vv \in V satisfies u→∗vu \xrightarrow{*} v. A common ancestor of two vertices uu and vv means a vertex w∈Vw \in V such that w→∗uw \xrightarrow{*} u and w→∗vw \xrightarrow{*} v. Assume that DD has at least one vertex. Prove that DD has a root if and only if every two vertices in DD have a common ancestor.

Browse the problem library