# A tree which each node selected as a root results in a different topology?

Show that, for every n >= 7, there exists a tree of n non-labeled nodes such that picking each of the n nodes as a root results in a different rooted tree.

• What are your ideas? What did you try? – Solomonoff's Secret Jun 27 '18 at 11:40
• @Solomonoff'sSecret I tried heuristically. I do not have any methodological answer to this. – Ninja Bug Jun 27 '18 at 15:29
• What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Jun 27 '18 at 16:27

Here is a hint. If the tree has size $> 1$ it will have to have a vertex with degree $\ge 3$ as otherwise it would be in a line and the two ends would be equivalent. So consider a tree with a vertex having 3 branches out of it. The branches will have to have different lengths or the end vertices of equal length branches would be equivalent.

What's the smallest number of vertices in a tree of that form? Can you see how to expand the tree maintaining the required property?

Also note that this approach proves that the sizes of trees having the mentioned property are 1 and $\ge 7$.

• I do not think that it is formally a proof, but now I can form trees with n >= 7 with your methodology. Thanks. – Ninja Bug Jun 27 '18 at 15:51
• @NinjaBug It's not a formal proof but it could easily be made into one by filling in the holes. – Solomonoff's Secret Jun 27 '18 at 16:27