draw a ordered tree of degree 3 with 7 vertices
Answers
Answer:
Any graph on nn vertices with kk automorphisms – ways its vertices can be mapped onto themselves to preserve the edges – has n!kn!k labellings. Applying this to the trees on seven vertices (the image below taken from Peter Steinbach's Field Guide to Simple Graphs, available on the OEIS under the links at A000055):
we see that the trees from left to right have the following numbers of automorphisms:
2,2,1,6,8,2,6,4,12,24,720
2,2,1,6,8,2,6,4,12,24,720
Dividing 7!=50407!=5040 by each number gives the number of labellings of each of these trees:
2520,2520,5040,840,630,2520,840,1260,420,210,7
2520,2520,5040,840,630,2520,840,1260,420,210,7
As expected, they add up to 75=1680775=16807.
Finding the order of the automorphism group of a tree
As an example, take the second tree from the left. There is only one order-3 vertex, so it must stay fixed in any automorphism. Three paths radiate from this vertex – one of length 4 that must also stay fixed, and two of length 1 that can be swapped. Multiplying the numbers together gives two automorphisms.
For the rightmost star, while the central hub must stay fixed, the six spokes can be permuted in any order, yielding 6!=7206!=720 automorphisms.