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

Question

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.

Answer 1

Here's an example of such a graph. If you remove the top vertex, this is just the Grötzsch graph with an edge removed. Since the the Grötzsch graph is minimal with respect to having chromatic number 4, the vertices of the removed edge must be the same color in any 3-coloring. We need this extra vertex at the top to make the graph maximal with respect to being triangle-free and 3-colorable . Since this is not maximal with respect to just being triangle-free, this graph has the property you want. (It's pretty easy to check the above claims, since this graph has a unique 3-coloring up to swapping the colors)