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

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.

## 2 Answers

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$$.

• Sorry, but I do not understand what you mean here. As I remarked briefly, $G$ is isomorphic to the Turán graph $T(10, 5)$ which has chromatic number 5. – Watercrystal May 31 '20 at 17:48

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$$

• The second part of this argument is not correct: the chromatic number is not a lower bound for the clique number of a graph. An example that demonstrates this is any odd cycle of size at least 5: They have chromatic number 3 but no cliques of size 3 (or larger). Also, the chromatic number of $G$ is usually denoted by $\chi(G)$ whereas $\omega(G)$ is used for its clique number. – Watercrystal May 31 '20 at 17:23
• to my understanding, its the maximal clique size in a graph... isnt it? – nir shahar May 31 '20 at 17:24
• OHHhh i see..... i have misunderstood it – nir shahar May 31 '20 at 17:24
• yea sorry i will fix it (even though its nice i found the clique number) – nir shahar May 31 '20 at 17:25
• now its supposed to be correct (with the nice addition of clique number proof) – nir shahar May 31 '20 at 17:36