(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.
Best Answer
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.
Next, convince yourself of the following.
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.