Problem $1.$ Path FH$.$

We'll say a Fibonacci heap is a path if it has size $n$ and height $n-1.$ A path has a single root, and every node

has at most one child.

$($a$)$ For $n1,$ show it is possible for a Fibonacci heap to be a path of size $n,$ with all nodes marked. That is$,$

describe a sequence of operations creating such a heap. You might present your construction inductively

$($base case, and then how to get from $n$ to $n+1).$ Include some diagrams.

$($b$)$ Argue that in any path of size $n,$ at least $n-2$ of the nodes have lost a child. $($Some nodes might not be

marked, so do not assume it was created by the sequence of operations you proposed in $($a$).)$

Reminder: CascadingCut does not mark a root when it loses a child.