Skip to main content
1 of 3
ARupinski
  • 5.2k
  • 1
  • 30
  • 51

Does this poset have a unique minimal element?

Recently I have been thinking about the following poset: the underlying set is $\mathcal{AFT}$ consisting of all (finite) automorphism-free undirected trees and the poset relation $\leq$ is defined by $T \leq U$ if $T$ can be obtained from $U$ by successively deleting one leaf node at a time in such a way that each intermediate tree is also an element of $\mathcal{AFT}$.

The smallest element of $\mathcal{AFT}$ is the seven node tree which is the Dynkin diagram of $E_7$ (and which I will therefore refer to simply as $E_7$ from herein):

http://upload.wikimedia.org/wikipedia/commons/a/a3/Dynkin_diagram_E7_%28no_numbers%29.png

So $E_7$ is certainly a minimal element in the above partial order.

Question: Does $(\mathcal{AFT},\leq)$ have a unique minimal element, namely $E_7$?

There are several equivalent formulations of this question which I have considered, hoping one of them might lead somewhere useful:

Question 2: Can every element of $\mathcal{AFT}$ be obtained by starting at $E_7$ and successively adjoining leaf nodes so that we remain in $\mathcal{AFT}$ at every stage?

>

Question 3: Is there an element of $\mathcal{AFT}$ besides $E_7$ such that deleting $any$ single leaf node results in a tree not in $\mathcal{AFT}$.

Question 3 in particular seems simple enough that it must have been answered somewhere before, but alas almost any search for 'automorphism-free' and 'trees' results in papers about the result that almost every tree has an automorphism or results on the fixed vertices/edges of trees under automorphisms.

Trying to construct a minimal example larger than $E_7$ for Question 3 keeps leading to near-misses where all but one leaf nodes' removal takes us outside $\mathcal{AFT}$, but after removing this one leaf node, there is still a sequence of removals remaining in $\mathcal{AFT}$ that leads back to $E_7$ which is the best evidence I have so far that Question 1 is true.

So, does anyone know where this might have been considered already, and if so, if the answer to Question 1 is affirmative?

ARupinski
  • 5.2k
  • 1
  • 30
  • 51