# k colouring vertices

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

• Do all $k$ colours have to be used? (So the answer is zero if $k\gt7$?) – bof Nov 28 '17 at 23:05
• adjacent vertices share an edge. I would start at some outer vertex and say it can have any of $n$ colours. The vertices adjacent to that will have $n-1$ colours. So those pairs of vertices will have $n(n-1)$ colourings. Keep going from there in a systematic way until all vertices are coloured. – stuart stevenson Nov 28 '17 at 23:06
• I assume you don't have to use all the colours. The counting is easy because the graphs are trees. Pick any vertex to colour first, and after that always pick a vertex next to some vertex you've already coloured. There are $k$ colours available for the first vertex, $k-1$ choices for every subsequent vertex, since you can't colour it the same as its neighbour. Use the multiplication rule. – bof Nov 28 '17 at 23:10
• So 5 & 6 are the only vertices considered adjacent – Mahlissa LECKY Nov 29 '17 at 0:00
• see this these is a lot of graph clusterisations with their polynomial formulas aside. – Abr001am Nov 29 '17 at 1:42

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.
• as for the second image all the outer vertices and the centre vertex can be coloured from k colours, leaving the remaining 3 vertices with k-1 colours? equating to $k(k-1)^3$ – Mahlissa LECKY Nov 29 '17 at 0:32
• No. The argument at the end of my answer is how you answer all of them. If a tree has $n$ vertices with $k$ colors available for each vertex, then there are $k(k-1)^{n-1}$ distinct colorings. – Laars Helenius Nov 29 '17 at 0:54