figure the resulting segment of the fibonacci heap after the decreasekey operation lost its second childso it is cut from the process stops heresince was unmarked the node is now marked the result is shown in figure notice that and which used to be marked nodesare no longer markedbecause they are now root nodes this will be crucial observation in our proof of the time bound proof of the time bound recall that the reason for marking nodes is that we needed to bound the rank (number of childrenr of any node we will now show that any node with descendants has rank (log nlemma let be any node in fibonacci heap let ci be the ith oldest child of then the rank of ci is at least proof at the time when ci was linked to xx already had (olderchildren ci- thusx had at least children when it linked to ci since nodes are linked only if they have the same rankit follows that at the time that ci was linked to xci had at least children since that timeit could have lost at most one childor else it would have been cut from thusci has at least children from lemma it is easy to show that any node of rank must have lot of descendants lemma let fk be the fibonacci numbers defined (in section by and fk fk- fk- any node of rank > has at least fr+ descendants (including itselfproof let sr be the smallest tree of rank clearlys and by lemma tree of rank must have subtrees of rank at least and plus another subtreewhich has at least one node along with the root of sr itselfthis gives  - si it is easy to show that sr fr+ minimum value for sr> of sr = (exercise ( )