Prüfer code generates a connected graph?

I'll describe a somewhat different version of the algorithm and leave it to you to see if they're equivalent.

Start with $n$ unmarked vertices (1 to $n$); each connected component has one unmarked vertex. Whenever we add an edge, we'll mark one of its endpoints, so that the newly formed connected component still has exactly one unmarked vertex. Then we'll make sure to only add edges between two unmarked vertices.

Since we make one mark for each entry of $P$, when we get to entry $a_i$, there are $n - i + 1$ unmarked vertices left, but only $n - i - 1$ entries of $P$ left (including $a_i$ itself), so at least two unmarked vertices do not appear in the rest of the sequence (pigeonhole principle!) Take the smallest one as $u$, add the edge $u a_i$, and mark $u$. The edge joined two unmarked endpoints, so it joins two different connected components. We know that $a_i$ was not marked at any previous step, because we always choose the endpoint to mark from among the vertices which aren't in the remainder of the sequence.

(On ProofWiki, the "list" is just the set of unmarked vertices.)