Introduction to Graph Theory · Problem 5.1

Trees and arborescences — Darij Grinberg

Mathematics — Graph Theory · trees-unique-paths

Problem

Let

G

be a multigraph that has no loops. Assume that there exists a vertex

u

G

such that for each vertex

v

G

, there is a unique path from

u

v

G

. Prove that

G

is a tree. [Remark: Pay attention to the quantifiers used here:

\exists u \forall v

. This differs from the

\forall u \forall v

in Statement T2 of the tree equivalence theorem (Theorem 5.2.4).]