0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What are your ideas? What did you try? $\endgroup$ – Solomonoff's Secret Jun 27 '18 at 11:40
  • $\begingroup$ @Solomonoff'sSecret I tried heuristically. I do not have any methodological answer to this. $\endgroup$ – Ninja Bug Jun 27 '18 at 15:29
  • $\begingroup$ 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. $\endgroup$ – D.W. Jun 27 '18 at 16:27
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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