Grinberg-Introduction-Graph-Theory · Problem 5.3

Trees and arborescences

Mathematics — Graph Theory · trees-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

. ((a)) Prove that if

T

has

k

leaves (for some

k \in \mathbb{N}

), then

T

has at most

k-2

branch vertices. ((b)) Prove that

T

has two distinct leaves

u

and

v

such that the path from

u

v

contains at most one branch vertex.