Let $T = (V, E)$ be a tree with a set of vertices $V = [7]$ and a set of edges:
$$E = \{1, 2 \}, \{1, 3 \}, \{1, 4 \}, \{2, 5 \}, \{3, 6 \}, \{4, 7 \}$$
In how many significantly different ways (with respect to the group of automorphisms of a graph $T$) the vertices of a tree $T$ can be colored using three colors?
*Coloring here means any function that assigns colors to the vertices from the three-element set
*Bijection $g : V \xrightarrow[1-1]{on} V$ is an automorphism of the graph $T$ if for any vertices $v, w \in V$ we have: $$\{v, w \} \in E \iff \{g(v), g(w) \} \in E$$
**Hint: start by justifying that if $g : V \xrightarrow[1-1]{on} V$ is an automorphism graph $T$, then for every $v \in V$ we have: $d(v) = d(g(v))$.
As I understand that, we have such a tree:
The definition of coloring is pretty straightforward: we just color every vertice in one of $3$ colors.
I don't know how to justify the hint, but I know that the definition of automorphism with added hint means that every tree of the same 'structure' with different combination of vertices (labels of the vertices) is considered the same as long as we preserve the degrees of vertices. Therefore we can only juggle the $3$ (whole) arms of a tree: $\{ 2,5 \} , \{ 3,6 \} , \{ 4,7 \}$.
Therefore we can use Burnside's Lemma.
We can change those arms in one of $3$ ways (I enumerate the $3$ arms with numbers pointing to their position from the RHS):
Shift to the right / left (changing places of all $3$ arms):
- $1$ step in right direction ($= 2$ steps in in left direction): $[1,2,3] \to [3,1,2] + [3,1,2] \to [2,3,1] + [2,3,1] \to [1,2,3]$, cycles: $x_3$, constant points: $3 \cdot 3^2$ (we choose one color for vertex $1$, then each arm has to be in the same colors)
- $2$ steps in right direction ($= 1$ step in in left direction): $[1,2,3] \to [2,3,1] + [2,3,1] \to [3,1,2] + [3,1,2] \to [1,2,3]$, cycles: $x_3$, constant points: $3 \cdot 3^2$ (we choose one color for vertex $1$, then each arm has to be in the same colors)
- $3$ steps in right direction ($= 3$ steps in in left direction): $[1,2,3] \to [1,2,3]$ (identity), cycles: $x_3$, constant points: $3 \cdot 3^6$ (we choose one color for vertex $1$, then each arm can have every combination of colors)
Swaps in pairs:
- first place with second place: $[1,2,3] \to [2,1,3] + [2,1,3] \to [1,2,3]$, cycles: $x_2$, constant points: $3 \cdot 3^2 \cdot 3^2$ (we choose one color for vertex $1$, then we choose the colors for the arm that stays in place, then for the arms that swap their places)
- first place with third place: $[1,2,3] \to [3,2,1] + [3,2,1] \to [1,2,3]$, cycles: $x_2$, constant points: $3 \cdot 3^2 \cdot 3^2$ (we choose one color for vertex $1$, then we choose the colors for the arm that stays in place, then for the arms that swap their places)
- second place with third place: $[1,2,3] \to [1,3,2],+ [1,3,2] \to [1,2,3]$, cycles: $x_2$, constant points: $3 \cdot 3^2 \cdot 3^2$ (we choose one color for vertex $1$, then we choose the colors for the arm that stays in place, then for the arms that swap their places)
At the end we get:
$$\frac{1}{6} \left( 3 \cdot 3^2 + 3 \cdot 3^2 + 3 \cdot 3^6 + 3 \cdot 3^2 \cdot 3^2 + 3 \cdot 3^2 \cdot 3^2 + 3 \cdot 3^2 \cdot 3^2 \right) = \frac{1}{6} \left( 3^3 + 3^3 + 3^7 + 3^5 + 3^5 + 3^5 \right) = \frac{1}{6} \left( 27 + 27 + 2187 + 243 + 243 + 243 \right) = 495$$
Is that correct? How to justify the hint?