Introduction to Graph Theory · Problem 5.18

Trees and arborescences — Darij Grinberg

Mathematics — Graph Theory · arborescences-acyclic-digraphs

Problem

Let D=(V,A,ψ)D = (V, A, \psi) be a multidigraph that has no cycles. Let r∈Vr \in V be some vertex of DD. Prove the following: (a) If deg⁡−u>0\deg^- u > 0 holds for all u∈V∖{r}u \in V \setminus \{r\}, then rr is a from-root of DD. (b) If deg⁡−u=1\deg^- u = 1 holds for all u∈V∖{r}u \in V \setminus \{r\}, then DD is an arborescence rooted from rr.

Browse the problem library