Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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
up vote 1 down vote accepted

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.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.