0
$\begingroup$

I was looking at the proof of the following result:

Let $n\geq 2$,the number of spanning trees in the complete graph $K_n$ is $n^{n-2}$.

The proof uses a bijection between $T$ ,the set of all spanning trees of $K_n$ and $A$, the set of all sequences $(a_1,a_2,...,a_{n-2})$ with $1\leq a_i\leq n$ for all $i$.The bijection is given by the Prufer code.

The forward map is clear to me.

We will look at all leaf nodes and pick the one with minimal numbering.Then we will delete the vertex and the associated edge and take a note of the neighboring vertex/node.We will continue in this way and finally we will end up getting two nodes connected with one edge.Thus we obtain $(a_1,a_2,...,a_{n-2})$.

For example,look at the following graph:

enter image description here

Then following the algorithm we get something like:

enter image description here

So,the Prufer sequence is $(1,8,3,1,4,4,8)$.

Now I am having problem in decoding the sequence and forming a tree.

The algorithm is to choose minimal $b_1\notin (a_1,a_2,...,a_{n-2})$ and join $b_1a_1$.Then take minimal $b_2\neq b_1 $ and $b_2\notin (a_2,a_3,...,a_{n-2})$ and join $b_2a_2$ ,then take minimal $b_3\neq b_1,b_2$ and $b_2\notin (a_3,a_4,...,a_{n-2})$ and join $b_3a_3$ and proceed in this way.

But applying this algorithm on $(1,8,3,1,4,4,8)$,I am not getting the same tree.

Can someone tell me where I am making the mistake?

$\endgroup$
6
  • 1
    $\begingroup$ Well, your Prüfer code is correct, so it's hard to tell where you're making a mistake in the part of your work that you did not show :) $\endgroup$
    – Misha Lavrov
    Commented Dec 8, 2022 at 4:48
  • $\begingroup$ From your description, it's possible that you're missing an initial step: before you begin this algorithm, you should append $n$ (in this case, $9$) to the Prüfer code, getting $(1,8,3,1,4,4,8,9)$. $\endgroup$
    – Misha Lavrov
    Commented Dec 8, 2022 at 4:53
  • $\begingroup$ @MishaLavrov But why should I append $9$ then the sequence will no longer be an $n-2$ length sequence. $\endgroup$
    – Kishalay Sarkar
    Commented Dec 8, 2022 at 5:05
  • 1
    $\begingroup$ A didactic example here $\endgroup$
    – Jean Marie
    Commented Dec 8, 2022 at 9:21
  • 1
    $\begingroup$ @JeanMarie Thank you,I have to append the number not in the list to the tail of the list along with removing the head of the list. $\endgroup$
    – Kishalay Sarkar
    Commented Dec 8, 2022 at 16:25

0

Reset to default

You must log in to answer this question.