# Prüfer code generates a connected graph?

I'm reading the ProofWiki page which describes the construction of a labeled tree from its Prüfer sequence, and am having trouble understanding this section:

The fact that T is in fact a tree follows from the fact that:

a) T has n nodes and (from the method of construction) n−1 edges;
b) Each new edge connects two as yet unconnected parts of T


Specifically, I don't follow claim b) above, that each new edge connects two as yet unconnected parts of $T$. I'm trying to show that it's true as follows:

At a given step $k$, suppose that we are adding the edge $e_k = \{a_k,b_k\}$ to the graph $G_{k-1}$ with edges $e_1,\dots,e_{k-1}$, then if $a_k$ and $b_k$ were already in the same connected component, there would be a path from $a_k$ to $b_k$ in $G_{k-1}$, which together with $e_k$ gives a cycle in $G_k$. I am hoping to somehow deduce a contradiction from this, but am not really sure where to take this argument.

Any help is appreciated!

-
Not sure what you don't understnad - the construction itself, or the claim that a graph on $n$ vertices with $n-1$ edges, where each edge connects two yet unconnected parts of $G$ is a tree? – gt6989b Apr 25 '13 at 17:14
@gt6989b I edited my question, hopefully that makes it clearer. – Jonas Apr 25 '13 at 17:21

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.