The question is asking for each of the following four trees, how many different ways are there of colouring the vertices with $k$ colours so that no two adjacent vertices are coloured the same colour?
I am really new to this kind of content in combinatorics. I know how to approach this question when actual colours are given, but when it comes to n colours i get confused when they say no two adjacent vertices.
How many different ways are there of coloring the
vertices with k colors such that adjacent vertices are colored with different colors and so that two colorings of the graph are considered different if there is no rearrangement of the vertices so that they look the same
here i don't know what hes asking for when he says without rearrangement
Best Answer
For your first graph, the answer is dependent upon the color choices you make for vertex 1 and vertex 2. There are $k^2$ ways to color the two vertices, but if the vertices share the same color (there are $k$ ways to do this), then the remaining vertices can all be colored any of the remaining $k-1$ colors independently, so you have $k(k-1)^5$ ways to do this. If the two vertices have distinct colors (there are $k^2-k$ ways to do this), then the vertex adjacent to both vertices can be colored $k-2$ ways and the remainder can each be colored $k-1$ ways, for a total of $(k^2-k)(k-1)^4(k-2)$ ways. Thus we have a total of $$ k(k-1)^6 $$ distinct colorings.
But this formula should suggest a different argument: pick a vertex and color it ($k$ ways to do this) and then each subsequent vertex always has exactly $k-1$ choices for a color.