In CLRS's Introduction to Algorithms 3rd edition P.525, when it analyzes the size($x$)'s lower bound, there is a sentence that I quote as "because adding children to a node cannot decrease the node’s size, the value of $s_k$ increases monotonically with $k$". But in fact, I think I can give a counterexample to show that $s_k$ does not necessarily increase monotonically with k.
In the following graph, the degree of the node with key 1 is 2, and there is no other node with degree of 2. So $s_2=8$. Similarly, $s_3=6$. But now $s_3$ is less than $s_2$ which means $s_k$ is not monotonically increasing with $k$ at all.
2 - 0 - 4 - 2 - 5 - 8 - 7 - 1 | / \ 8 2 9 / | \ 10 14 16 | | 11 15
The heap can be derived from an unordered binomial subtree by executing a series of cuts and cascading-cuts.
I want to know whether the above structure is a valid Fibonacci heap. If so, then it is also a valid counterexample.