MathDB

Let T be a finite tree graph that has more than one vertex. Let s be the largest number of vertices of a subtree

X \subset T

for which every vertex of X has a neighbor other than X. Let t be the smallest positive integer for which each edge of T is contained in exactly t stars, and each vertex of T is contained in at most 2t - 1 stars. (That is, the stars can be represented by multiplicity.) Prove that s = t. Note: a star of T is a vertex with degree

\geq

3 , including its neighouring edges and vertices.

Problem Statement