Existence of infinite subsequence of trees assuming two tree operations

125 Views Asked by At

Assume two operations on rooted trees:

  1. contract an edge: choose an edge $E$, join two vertices adjacent to $E$
  2. grow a leaf: choose any vertex and connect it to a new leaf

Starting with any rooted tree, using these operations we get an infinite sequence of trees.

Does the sequence always contain a tree $T$ such that there is infinitely many trees in the sequence with $T$ as a subgraph?

It is a variation of question Existence of infinite subsequence of trees with a subtree contained in the sequence with added limitation on succesive items in the sequence. This variation now maybe could relate to The hydra game.

1

There are 1 best solutions below

0
On BEST ANSWER

If you want your operations to be 1,2,1,2,1,2,1,2, then such an order will ensure that all your trees will have either $n$ or $(n+1)$ vertices, and since there is only a finite number of non-isomorphic trees of size $n$, you will get infinitely many copies of at least one of them.

On the other hand, if the order of operations is unconstrained, then an adaptation of the example of Robert Israel still works:

a sequence of non-isomorphic trees

and so on...

I hope this helps $\ddot\smile$