I am studying the operations of the Fibonacci heap. While going through min-extraction operation every step and its complexities are fairly clear to me. In short, it is:
The potential before extracting the minimum node is t(H) + 2m(H), and the potential afterward is at most (D(n) + 1) + 2m(H), since at most D(n) + 1 roots remain and no nodes become marked during the operation. The amortized cost is thus at most
O(D(n) + t(H)) + ((D(n) + 1) + 2m(H)) - (t(H) + 2m(H))
= O(D(n)) + O(t(H)) - t(H)
= O(D(n))
Source: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap21.htm
I don't understand this particular line: "since at most D(n) + 1 roots remain" after consolidation. How do we derive this result? Can not it happen that all of the t(H)+D(n)-1 root nodes have different degrees so all of them remain?