A Prufer code with 2 unknowns Given a labled tree G with the vertices $\lbrace{1,2,3,4,5,6}\rbrace$,
And the Prufer code of G is $(1,x,2,y)$, and $x,y\in \lbrace{1,2,3,4,5,6}\rbrace$. Which of the following is true:


*

*$x,y\in \lbrace{3,4,5,6}\rbrace$ and $x\neq y$

*$x,y\in \lbrace{3,4,5,6}\rbrace$ but it might be that $x=y$

*$x,y\in \lbrace{1,2,3,4,5,6}\rbrace$ and $x\neq y$

*$x,y\in \lbrace{1,2,3,4,5,6}\rbrace$ 

*Impossible: G's Prufer code cannot be in the length of 4


I think 5 can be easilly ruled out, and I think also 1, but I couldn't figure out a method for solving this. Tried to reconstruct the tree but got confused from the different possibilites...

The reason Prüfer codes are so useful is that they provide a bijection between the $n^{n-2}$ labeled trees on $n$ vertices and the $n^{n-2}$ sequences of $n-2$ elements from $\{1,2,\dots,n\}$. Every possible sequence of this form gives a unique labeled tree, and every labeled tree has a unique Prüfer code.
In this case, $n=6$ and every $4$-tuple $(a,b,c,d)$ with $a,b,c,d \in \{1,2,3,4,5,6\}$ corresponds to a labeled tree; in particular, any $x,y \in \{1,2,3,4,5,6\}$ give valid Prüfer codes $(1,x,2,y)$.
