Chromatic number of a graph with $10$ vertices each of degree $8$?

Question

I have simple graph G on 10 vertices the degree of each vertex is 8. I need to determine the chromatic number of G. I tried drawing and all but it seems there is a trick needs to be used.

Answer 1

Let $G = (V, E)$ be a simple graph like you described (which is unique up to isomorphism and known as the Turán graph $T(10, 5)$, by the way). Note that the maximal degree possible in a graph with $10$ vertices is $9$ and thus, for every vertex $v$ in $G$ there exists a unique vertex $w \ne v$ which is not connected to $v$ and the two vertices share a neighborhood, i.e. $N(v) = N(w)$. Therefore, $v$ and $w$ may be colored using the same color. This however implies that the chromatic number of $G$, denoted by $\chi(G)$, satisfies $\chi(G) \leq 5$ since we can take all such pairs $\{v, w\}$ as described above and assign every such pair a unique color (using 5 colors in total).

To see that $\chi(G)$ cannot be less than $5$ consider the (induced) subgraph $G'$ of $G$ that we get by removing one vertex of every such pair $\{v, w\}$ as described above (that means $vw \notin E$). We find that $G'$ consists of 5 vertices and is complete, therefore implying that $G$ contains a clique of size $5$ and giving us $\chi(G) \geq 5$.

Hence we have shown $\chi(G) = 5$.

Answer 2

Let $v$ be some node. then it had 8 neighbors, and there is exactly one node $u$ which is not connected to $v$. Notice that also $u$ has 8 neighbors, and thus $v$ is the only node not neighboring it.

We can partition the graph into 5 groups of 2 nodes $V_1=\{v_1,u_1\},...,V_5=\{v_5,u_5\}$, where every group's node's are not connected to each other (there is no edge $(v_i,u_i)$) but they are connected to everything else.

This is a 5-partition of the graph, and we can give a different color for each pair. Thus the chromatic number satisfies $\chi (G) \le 5$. But if we use less than 5 colors, say, 4 colors, then there must be two groups with a node that has the same color in both, but since that they are connected we get a contradicton to the coloring. Thus $\chi (G) \ge 5$ and finally $\chi (G) =5$

---

From here, it is a solution to the clique number, and not the chromatic number:

Since we have 5 groups, Then choosing one node from each group guarantees to give us a clique of size 5. So if we define $\omega (G)$ to be its chromatic number, then in this case we have proven that $\omega (G) \ge 5$.

Lets assume toward contradiction that $\omega (G) > 5$. Then there exists a clique of size at least 6. Let that clique be $\{w_1,..,w_6\}$. From the pigeonhole principle, we have that there are two $w_i, w_j$ in the same $V_k$. But then there is no edge between them, in contradiction that this is a clique.

Thus $\omega (G) \le 5$ and finally combining those two together we have $\omega (G)=5$