On the structure and deficiency of kk-trees with bounded degree

A proper edge colouring of a graph with natural numbers is consecutive   if colours of edges incident with each vertex form a consecutive interval of integers. The deficiency def(G)def(G) of a graph GG is the minimum number of pendant edges whose attachment to GG makes it consecutively colourable. Since all 1-trees are consecutively colourable, in this paper we study the deficiency of kk-trees for k≥2k≥2. Our investigation establishes the values of the deficiency of all kk-trees that have maximum degree bounded from above by 2k2k, with k∈{2,3,4}k∈{2,3,4}. To obtain these results we consider the structure of kk-trees with bounded degree and the deficiency of general graphs of odd order. In the first case we show that for n≥2k+3n≥2k+3 the structure of an  nn-vertex kk-tree with maximum degree not greater than 2k2k is unique. In the second one we prove that for each nn-vertex graph GG of odd order the inequality def(G)≥12(|E(G)|−(n−1)Δ(G)) holds. Both last mentioned results seem to be interesting in their own right.