I want to construct a graph $G$ such that $G$ does not contain $K_r$ but $G$ is not $(r − 1)$-partite for each $r \geq 3$. ($|G|$ is not fixed)
I think should be a start with a path but a path is bipartite. Can someone give me some idea to construct it?
On
I expand on Misha Lavrov's answer by presenting a more formal proof of that idea.
Define $G_3 = C_5$. Then let $G_r$ be the graph $G_{r-1}$ with a new vertex, connected to all the existing vertices.
Now we prove that $G_r$ satisfies our properties, both can be done by induction.
Claim 1: $G_r$ has chromatic number $\chi(G_r) = r$ (i.e. is not $(r-1)$-partite).
Proof: We can verify $\chi(G_3)=\chi(C_5) = 3$. If $\chi(G_{r-1}) = r-1$, then $\chi(G_r)$ must be $r$, since we connect the new vertex to all previous vertices, which have to be coloured with $r-1$ distinct colours. Done by induction.
Claim 2: $G_r$ has $5$ vertices with degree $r-1$, and all other vertices have larger degree than $r-1$.
Proof: All of $G_3=C_5$'s $5$ vertices have degree $3-1=2$. Its other $0$ vertices have larger degree vacuously.
If this holds for $G_{r-1}$, then the $5$ vertices with degree $r-2$ become the $5$ vertices with degree $r-1$ in $G_r$. All other existing vertices started with a degree larger than $r-2$, and hence have degree larger than $r-1$ in $G_r$. The new vertex has degree $|G_r|-1=r+1>r-1$. Done by induction.
Claim $2$ is a stronger statement than saying $K_r \not \subset G_r$ for $r>5$, since $K_r$ will have $r$ vertices with degree $r-1$, but $G_r$ has has $5<r$ of them. Combining this with claim $1$ gives the result for $r>5$.
We can check manually that $G_3$, $G_4$, $G_5$ satisfy the property.
Not being $(r-1)$-partite is equivalent to having chromatic number at least $r$. So we want to find a graph $G$ with $\chi(G) \ge r$, but not for the "trivial reason" of containing a $K_r$.
The simplest such graph is the $5$-cycle $C_5$. This does not contain $K_3$ (a triangle) but $\chi(C_5) = 3$.
From here, we want to increase the chromatic number without creating big cliques. We can go up to $r=4$ by adding a vertex adjacent to all the existing ones, creating the wheel graph $W_6$:
This does not contain $K_4$, but $\chi(W_6) = 4$.
We can generalize this approach, for one way to solve the problem.
In fact, almost any graph will work - literally. If you take a random graph on the vertices $v_1, v_2, \dots, v_n$, the largest clique it will contain, almost always, will have about $2 \log_2 n$ vertices. However, the chromatic number is much larger than this: by the same token, the largest independent set will have about $2 \log_2 n$ vertices, which means at most that many vertices can have any color, and therefore the chromatic number will be at least $\approx \frac{n}{2 \log_2 n}$.