I was solving a question related to k-tuple graph colouring. The text states that, A k-tuple colouring of a graph G is an assignment of a set of k different colours to each of the vertices of G such that no two adjacent vertices are assigned a common colour. We are supposed to find the smallest positive integer n, such that G has a k-tuple colouring using n colours.
So let's say we have a graph G, such that V = {a, b, c, d, e, f, g} and E = {(a,b), (a,c), (b,d), (c,d), (b,e), (c,f), (e,d), (f,d), (e,g), (f,g), (a,g), (b,c), (e,f)}. The value of k is 2.
Now, according to the definition given above, the value of n should be 8, but the book says it is 7, how is it so ?
Here is a $2$-tuple colouring of $G$ with $7$ colours.
$A\to$ red, orange
$B\to$ yellow, green
$C\to$ blue, indigo
$D\to$ red, violet
$E\to$ blue, indigo
$F\to$ orange, yellow
$G\to$ green, violet
Here's one way you might approach this problem. The graph $G$ contains a $5$-cycle $A-B-D-F-G-A$ and two more vertices $C,E$ which are joined to most of the vertices of the $5$-cycle but not to each other. So the problem is to colour the $5$-cycle with $5$ colours (instead of the obvious $6$ colours); then we have $2$ colours left for $C,E$ and these 2 are sufficient which can be checked when drawing the graph or by other methods. Then we only needs to care the coloring of 5-cycle.
So lets start by giving colours $1,2$ to $A$ and colours $3,4$ to $B.$ Now lets think a step ahead: if we use $4$ different colours on $D$ and $G,$ then we won't be able to colour $F.$ So $D$ and $G$ must have a common colour, call it $5.$ So let's colour $D$ with $1,5$ and $G$ with $3,5$ and then $F$ can be coloured $2,4.$