Introduction to Graph Theory · Problem 5.16

Trees and arborescences — Darij Grinberg

Mathematics — Graph Theory · centers-of-trees

Problem

Let

T

be a tree. Let

\mathbf{p} = (p_0, *, p_1, *, p_2, \ldots, *, p_m)

be a longest path of

T

. (We write asterisks for the edges since we don't need to name them.) Prove the following: (a) If

m

is even, then the only center of

T

p_{m/2}

. (b) If

m

is odd, then the two centers of

T

are

p_{(m-1)/2}

and

p_{(m+1)/2}