Packing tree degree sequences (Q2175807)

A degree sequence is a list of non-negative integers, \(D = d_1, d_2,\dots, d_n\). It is called graphical if there exists a simple graph \(G\) such that the degree of the \(i^{\text{th}}\) vertex is \(d_i\); \(G\) is then said to be a realization of \(D\). A degree sequence \(D = d_1, d_2, \dots, d_n\) is a tree degree sequence if all degrees are positive and \(\sum_{i=1}^n d_i = 2n- 2\). A degree sequence is a path degree sequence if two of its degrees are 1 and all other degrees are \(2\). The paper consideres the problem of packing tree degree sequences: given \(k\) tree degree sequences, do they have simultaneous (i.e. on the same vertices) edge-disjoint realizations? Also it conjectured that this is true for any arbitrary number of tree degree sequences whenever they share no common leaves (degree-1 vertices). This paper gives a proof for \(4\) tree degree sequences and a computer-aided proof for \(5\) tree degree sequences. The conjecture for arbitrary \(k\) is also considered. It is proved that \(k\) tree degree sequences without common leaves and at least \(2k- 4\) vertices which are not leaves in any of the trees always have edge disjoint tree realizations.