Let be the number of nests evacuated on night , and let .
Removing all leaves from a tree leaves a smaller connected tree, unless nothing remains. If every vertex of a tree has degree at most one, it has one vertex or two adjacent vertices. Therefore, the last layer must have size , and its edges are uniquely determined. No night before can be empty: every nonempty tree has a leaf.
Now rebuild the tree backwards. Suppose all layers after night have already been built, with vertices. A vertex of layer was a leaf while this later tree was still present, so it must have exactly one edge to a later vertex. Two vertices of layer cannot be adjacent: two adjacent leaves would form a separate component. Thus, rebuilding this layer means choosing one later parent for each of its labeled vertices.
Which later vertices must receive a child? When , each vertex of layer has degree one in the later tree. It must receive at least one child from layer ; otherwise, it would already be evacuated on night . Vertices of higher layers already have degree at least two and need no additional child.
There is one exception. If the later tree is a single vertex, that vertex has degree zero and must receive at least two children. All parents are then forced, so this step has one choice if , and no choices otherwise.
These conditions are also sufficient. Adding vertices with one parent preserves the tree, makes exactly the new layer its leaves, and makes every later vertex survive the next evacuation. Repeating this construction gives exactly the prescribed nights.