How to prove that the smallest asymmetric tree has at least 7 vertices? Find the smallest possible number of vertices an asymmetric tree can have (i.e. prove that no smaller tree can be asymmetric).
I think that the answer is 7, but I don't know how to prove it.
 A: If a tree has exactly two leaves, then it is a path, and so is not asymmetric. So any such tree has at least three leaves.
If any two of these leaves have a common neighbor, then we can switch those two leaves, and this gives a symmetry. Thus, the three leaves, call them $v_1,v_2,v_3$ have pairwise distinct neighbors $w_1,w_2,w_3$. In particular, the graph has at least six vertices. Suppose it had exactly six. Then $w_1,w_2,w_3$ cannot themselves be leaves, so they must connect to each other. There is up to isomorphism only one way to do this: $w_2$ connects to $w_1$ and $w_3$. But this graph has an automorphism: we can switch $w_3$ and $v_3$ with $w_1$ and $v_1$, respectively.
Thus, any graph with no automorphism must have at least seven vertices.
A: I suppose a tree has at least 2 vertices, right?
You are right about $7$ and I believe the proof of this fact is a case by case verification!

There are in total $13$ trees with vertices ranging between 2 and 6 (1 with 2 vertices, 1 with 3, 2 with 4, 3 with 5 and 6 with 6 vertices).
