# Graph which is maximal triangle-free 3-colorable, but not maximal triangle-free

I am looking for a graph which is maximal triangle-free 3-colorable, but not maximal triangle-free. Here a graph which is maximal triangle-free 3-colorable is a graph where the addition of any edge violates either the triangle-free condition or the 3-colorable condition.

The possible counterexample necessarily has a pair of vertices with distances $$\geq 3$$ (in fact no two vertices can have distance greater than 3) where every 3-coloring of the graph has those two vertices being the same color. Some stronger things can be proven about the counterexample, such as every neighbor of one of those aforementioned vertices must be connected to a neighbor of the other vertex, and vice versa (otherwise the distance between a vertex and a neighbor of the other is $$\geq 3$$, so they must be the same color, but this contradicts that the original two vertices are always the same color). If this explanation is unclear I can elaborate more.

It seems if there exists a triangle-free graph which is 3-colorable and two vertices have to be different colors, one could use this to define the desired graph. Another note is that the graph must be at least 11 vertices - adding in the edge between the two vertices results in a triangle-free graph with chromatic number 4, the smallest example of which is the Groetzsch graph.

• You have repeated maximal triangle free twice, could you clarify? Aug 12 '20 at 6:53
• By maximal triangle-free, I mean a graph which is triangle-free, and the addition of any edge creates a triangle, not maximal in terms of edge count (which are the complete bipartite graphs) Aug 12 '20 at 7:15
• From your title you seem to be looking for a graph which is maximal triangle-free, but not maximal triangle-free. Do you maybe mean something else for one of these? Aug 12 '20 at 7:30
• The graph should be maximal with respect to both properties - triangle-free and 3-colorable Aug 12 '20 at 7:33
• dosent a $5$-cycle do the job? Aug 12 '20 at 8:03