Let $A_i$ be a complete graph $K_n$ for all $1\le k\le 5$ and let $B_n$ be a graph which obtain from vertex disjoint union of $A_1,A_2,...,A_5$ by adding all possible edges between $A_i$ and $A_{i+1}$, where $A_6=A_1$. Let $\phi(B_n)$ be the chromatic no. of $B_n$, show that $\phi(B_n)$=smallest integer greater than or equal $5n/2$.
The definition of chromatic number i use here is the minimum number of colours required to colour the vertice of the grap such that no 2 adjacent vertices share same colour.
I can find that $B_1= 3 $ and $B_2=5$ with little difficulties but i have no idea how they can come up with smallest interger greater than or equal to $5n/2$. Any assit would be appreciated.Thanks!
We show $\phi(B_n)\leq \lceil\frac{5n}{2}\rceil$ To do this we give an arrangement. Color the vertices in the first part with the numbers from 1 to n, color those in the second part with the numbers n+1 to 2n. Color those in the third part with numbers $\lceil\frac{n}{2}\rceil$ to $n$ and $2n+1$ to $\lceil\frac{5n}{2}\rceil$. Color those in the fourth part with numbers $1$ to $\lfloor\frac{n}{2}\rfloor$ and $n+1$ to $\lceil\frac{3n}{2}\rceil$. Finally color those in the fifth part with colors $\lceil\frac{3n}{2}\rceil+1$ to $\lceil\frac{5n}{2}\rceil$.
To show $\phi(B_n)\geq \frac{5n}{2}$ Assume the contrary, so that the number of colors is less than $\frac{5n}{2}$ in some coloring, now notice there are $5n$ vertices. So we can conclude one color appeared in at least three vertices. But if it did it must have appeared in three different parts, but if you take three different parts there must be two consecutive parts, a contradiction since that would make those vertices adjacent.