# Hamiltonian cycles in the square of a caterpillar tree

According to this paper, there exists a proof that the square of a tree has Hamiltonian cycles iff it is a caterpillar tree. Wikipedia also states a similar point:

They are the trees whose square is a Hamiltonian graph. That is, in a caterpillar, there exists a cyclic sequence of all the vertices in which each adjacent pair of vertices in the sequence is at distance one or two from each other, and trees that are not caterpillars do not have such a sequence. A cycle of this type may be obtained by drawing the caterpillar on two parallel lines and concatenating the sequence of vertices on one line with the reverse of the sequence on the other line.

Source: Wikipedia

1. I don't understand Wikipedia's explanation of obtaining Hamiltonian cycles in the square of a caterpillar tree. What does it mean to "draw the caterpillar on two parallel lines"?

2. How to count the number of Hamiltonian cycles (from a single source) in the square of a caterpillar tree?

I read somewhere that the answer to this would be: $2 \times n_1!\times \cdots \times n_k!$, where $n_1, \ldots, n_k$ are the number of leaves attached to each node on the path defining the caterpillar tree. The only exception is a star, when the answer is simply $(n - 1)!$ However, I am unable to understand how these expressions were derived.

Then the formula comes from the fact that you can rearrange each set of leaves in any order to get a different cycle, and the factor of $2$ is presumably because you could go in either direction, giving two different cycles for each ordering. In the star there is no extra factor of $2$, because going in the opposite direction is the same as just reversing the order of the leaves.