# Why must a triangle-free 4-chromatic graph have at least 11 vertices?

(For this problem, I am talking about undirected graphs)

A 4-chromatic graph is graph which requires at least 4 colors for a proper coloring. A proper coloring involves coloring all the vertices so that any pair of adjacent vertices are of different colors. (Note: Adjacent vertices are vertices that have an edge connecting the two together)

A triangle-free graph is a graph in which there are no cliques of size 3 (a group of 3 vertices in which they are all adjacent to each other).

I am approaching by proof by contradiction, but I have to say I have little to show.

• Hi. Can you show a bit of your work on this so far? Or at least some definitions: this way it is easier to help you! – MattAllegro May 12 '14 at 19:44
• Much better! I do not know graph theory at all but this will help other users in answering your question properly. – MattAllegro May 12 '14 at 20:20

The following is probably not the slickest way, but here it is anyway. Note that there are some details I'm leaving for you to fill in. Of course whenever I say "coloring," I always mean a proper coloring.

For a graph $G$, let $\Delta(G)$ denote the maximum degree amongst all the vertices in $G$. Recall the following famous result.

Brook's Theorem: Let $G$ be a connected graph. If $G$ is either a cycle of odd length or a complete graph, then $\chi(G)=\Delta(G)+1$. Otherwise, $\chi(G)\leq \Delta(G)$.

Next, convince yourself of the following.

Lemma: If $H$ is a triangle-free graph on $5$ or fewer vertices, then either $H$ is a cycle of length $5$ or $\chi(H)\leq 2$.

So now suppose you are given a triangle-free graph $G$ on $10$ or fewer vertices. We may as well assume that $G$ is connected and has at least $6$ vertices. Furthermore, we can assume that $\Delta(G)\geq 4$.

Let $v$ be a vertex of degree $\Delta(G)$, let $A$ be the neighbours of $v$. Note that $A$ is an independent set (i.e, no edges exist between vertices in $A$). Let $B$ be the subgraph induced by the non-neighbours of $v$.

If $\Delta(G)>4$, then $B$ has at most $4$ vertices. By the lemma, the vertices of $B$ can then be colored using two colors, say red and blue. Next, we can color all vertices of $A$ green. Finally, since $v$ is not adjacent to any vertex in $B$, we can color it red. Thus we've found a $3$-coloring of $G$.

If $\Delta(G)=4$, and $B$ is not a cycle of length $5$, then proceed as in the previous paragraph to obtain a $3$-coloring of $G$. So we may now assume that $\Delta(G)=4$ and that $B$ is a cycle of length $5$. Note that this means $G$ has $10$ vertices. In particular, we now know that any triangle-free graph on at most $9$ vertices is $3$-colorable.

Now, if any vertex $w$ in $G$ has $\deg(w)\leq 2$, delete it. The resulting graph $G-w$ has $9$ vertices and so we can color it with three colors. But since the deleted vertex has at most two neighbours in $G$, this means that such a coloring of $G-w$ can be extended to a coloring of $G$ using three colors, and we're done. So now assume all vertices in $G$ have degree at least $3$. Since $G$ is triangle-free, this means that every vertex in $A$ has exactly two neighbours in $B$. So at this point, $G$ looks like:

Suppose a vertex in $b\in B$ is adjacent to all four neighbours in $A$. Since there are no vertices of degree $2$, the two neighbours of $b$ are also adjacent to a vertex in $A$. But then $G$ would not be triangle-free, so no vertex in $B$ can be adjacent to all four vertices in $A$.

Suppose a vertex $b\in B$ has exactly three neighbours in $A$. This forces the two neighbours of $b$ in $B$ to be adjacent to the fourth vertex in $A$, and the neighbours of $b$ in $A$ to be adjacent to one of the two non-neighbours of $b$ in $B$. In a thousand words, $G$ looks like:

But now we can $3$-color $G$ as so:

Finally, we may suppose no vertex in $B$ has more than two neighbours in $A$. But since there are $8$ edges between $A$ and $B$, this means that exactly three vertices in $B$ have two neighbours in $A$. Hence two of these vertices must be adjacent, and so the graph looks like:

Color the vertices as so:

But since $G$ is triangle-free, this is actually a proper $3$-coloring.

I am not sure if this is a direct enough answer for you but this is related to the Mycielski construction.

In Sur le coloriage des graphs", Colloq. Math. 3: 161–162 Mycielski provided a construction of triangle free graphs having arbitrary chromatic number.

Later V. Chvátal (The minimality of the mycielski graph, Lecture Notes in Mathematics Volume 406, 1974, pp 243-246) showed that such graphs are minimal examples.