Introduction to Graph Theory · Problem 5.3

Trees and arborescences — Darij Grinberg

Mathematics — Graph Theory · tree-branch-vertices

Problem

Let

T

be a tree that has at least two vertices. A branch vertex of

T

means a vertex

v

T

such that

\deg v \geq 3

. • Prove that if

T

has

k

leaves (for some

k \in \mathbb{N}

), then

T

has at most

k - 2

branch vertices. • Prove that

T

has two distinct leaves

u

and

v

such that the path from

u

v

contains at most one branch vertex.