Talk:Prüfer sequence

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Low Priority
 Field:  Discrete mathematics


The figure on this page is not very useful for someone trying to understand Prüfer sequences. I believe it is too simple.

For instance, how would one proceed if the nodes labelled 3 and 4 were relabelled 4 and 3? Would the sequence then be 3335, or 3345? I presume the former because the later would result in a disconnected graph? It would be helpful if this were made explicit.

Ray 06:06, 26 February 2006 (UTC)

It says explicitly "remove the leaf with the smallest label". Therefore there is no ambiguity.


How you get the tree from the code? 150.244.52.8 (talk) 16:34, 19 January 2008 (UTC)


In the "Other Applications" section, there appears to be a mistake: in a complete n-order graph, every vertex has degree n-1. --Matt mcgill 15:44, 15 October 2007 (UTC)

Proof there is a 1-1 corespondence[edit]

Is someone willing to write the proof that indeed, each tree gets it own Prüfer sequence thus giving a injection? Stdazi (talk) 17:47, 19 June 2008 (UTC)

Removed merge proposal[edit]

I removed the merge proposal because Prüfer's code is entirely different concept than the one employed in Cayley's proof. —Preceding unsigned comment added by 86.3.42.126 (talk) 13:55, 14 August 2008 (UTC)

Pseudocode[edit]

That's not pseudo code, that's C without types. Tsuihark (talk) 21:24, 3 March 2009 (UTC)


I tried to remedy that (and also put in an algorithm that works). aibyou_chan (talk) 22:26, 10 February 2010 (UTC)

Algorithm to convert a Prüfer sequence into a tree[edit]

For those interested, the French article proposes a second method to do the decoding. The array of degrees is replaced with an array of nodes that have not been examined yet.

In the hope that helps, --MathsPoetry (talk) 12:43, 16 March 2012 (UTC)