Graph Coloring and Complete Graph If a graph is k-colorable, then does it imply that it must have a k-complete graph as it's subgraph? For example if a graph has chromatic no = 5, then is this sufficient to imply that it must have K5 as its subgraph?
Basically I am trying to solve this question of MIT 6.042, problem set 4 (2010):

Let ($s_1$, $s_2$, ..., $s_n$) be an arbitrarily distributed sequence of the number 1, 2, ..., n − 1, n. For instance, for n = 5, one arbitrary sequence could be (5, 3, 4, 2, 1).
Define the graph G=(V,E) as follows:
  
  
*
  
*V = {v1, v2, ..., vn}
  
*e = (vi, vj ) ∈ E if either:
a. j = i + 1, for 1 ≤ i ≤ n − 1
b. i = $s_k$, and j = $s_{k+1}$ for 1 ≤ k ≤ n−1
Prove that this graph is 4-colorable for any (s1, s2, ..., sn).
Hint: First show that that a line graph is 2-colorable. Note that a line graph is defined as follows: The n-node graph containing n-1 edges in sequence is known as the line graph $L_n$

My approach: Trying to prove by contradiction, I will assume that graph G is not 4-colorable, then it requires atleast 5 colours, this implies that there must be K-5 as a subgraph in G (Now here I am using a strong statement about which I am not sure). Then I will show that K-5 is not possible under the definitions of graph G, hence a contradiction.
Is this approach correct or is there a better one?
 A: I have been working on this same problem and found this older question on this forum.
Here is the link to the pdf for the problem set:
Problem Set 4
This is question 6 (a). Here is how I think you are supposed to answer it.
First you color the vertices 1 through n with 2 colors, say blue and red, just using the first set of edges like $(v_i,v_j)$ where $j=i+1$, $1 \le i \le n-1$.
So now the graph from vertex 1 to vertex n looks like this:
R-B-R-B-....
Now you have to add the edges $(v_{S_k},v_{S_{k+1}})$, $1\le k \le n-1$, one at a time adjusting the color of $v_{S_{k+1}}$ so it is different from the color of the vertices that it is connected to.
But there are only three possible vertices connected to the new vertex $v_{S_{k+1}}$. There are at most two from the original line and then also $v_{S_k}$. The two from the original line would be labeled $v_{S_{k+1}-1}$ and $v_{S_{k+1}+1}$.
So, as you add each edge $(v_{S_k},v_{S_{k+1}})$ you just have to pick at most a fourth color to color $v_{S_{k+1}}$, a different color from $v_{S_k}$, $v_{S_{k+1}-1}$ and $v_{S_{k+1}+1}$.
A: Consider the graph $G$ with $7$ vertices $x_0,x_1,x_2,x_3,x_4,v,w$ and $16$ edges: $x_0x_1$, $x_1x_2$, $x_2x_3$, $x_3x_4$, $x_4x_0$, $vx_0$, $vx_1$, $vx_2$, $vx_3$, $vx_4$, $wx_0$, $wx_1$, $wx_2$, $wx_3$, $wx_4$, $vw$. This graph does not contain a complete graph $K_5$. Its chromatic number is $5$: you will need $3$ colors to properly color the vertices $x_i$, and another color for $v$, and another color for $w$.
To solve the MIT problem: Color the vertex $v_i$, where $i=s_k$, with color $0$ if $i$ and $k$ are both even, $1$ if $i$ is even and $k$ odd, $2$ if $i$ is odd and $k$ even, $3$ if $i$ and $k$ are both odd.
A: Lemma1: A line graph is 2 colorable.
The proof is fairly straight forward.
Lemma2: The subgraph containing the odd vertices(v1,v3,v5,...) forms one or more non intersecting line graphs(non intersecting in the sense there are no common nodes in two line graphs)
Proof: We need to show that there doesn't exist a cycle, and we can use this along with the fact that a node can have at most 2edges in the subgraph
Lemma3: Lemma2 for the subgraph with even vertices.
Thm: The graph is 4-colorable
Pf: First take all the odd vertices. by lemma 2 we can color the odd vertices using 2 colors(say Black and White). Now using lemma 3 we can color the even vertices using 2 colors(different from odd)(say Red and Yellow). This covers all the edges from an odd to an odd vertex and even to even vertex without violating the coloring. What is left is the edges from odd to even vertex. This is clearly not violating the vertex coloring since odd vertex can have either black/white and even vertex can have either red/yellow. Hence the graph is 4-colorable.
