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.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ What are your ideas? What did you try? $\endgroup$– Reinstate MonicaJun 27, 2018 at 11:40
-
$\begingroup$ @Solomonoff'sSecret I tried heuristically. I do not have any methodological answer to this. $\endgroup$– Ninja BugJun 27, 2018 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, 2018 at 16:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
-
$\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$ Jun 27, 2018 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$ Jun 27, 2018 at 16:27