Consider the following graph In how many ways can we color t

Consider the following graph: In how many ways can we color the vertices of the graph with T colors if we start at vertex 1 and proceed in increasing order, and no two vertices connected by an edge can be the same color?

Solution

Label the vertices 1,2,3,4 adn 5.

1 can be coloured in T ways.

2 can also be coloured in T ways , as 1 and 2 are not connected by any edge.

Now here are only T-1 choices for 3 (excluding 1\'s colour)

4 can be colored in T-2 ways.(cant use 1 and 2 colours)

5 can be coloure in T-2 ways (excluding 2,3\'s colour).

So total number of colourings = T²(T-1)(T-2)²