Degree sets ofk-trees: Smallk

Ak-tree is ak-uniform hypergraph constructed from a single edge by the successive addition of edges each containing a new vertex andk−1 vertices of an existing edge. We show that ifD is any finite set of positive integers which includes 1, thenD is the set of vertex degrees of somek-tree fork=2, 3, and 4, and that there is precisely one such set,D={1, 4, 6}, which is not the set of degrees of any 5-tree. We also show for eachk≧2 that such a setD is the set of degrees of somek-tree provided only thatD contains some elementd which satisfiesd≧k (k−1)−2 [k/2]+3.