Triangle-Free and Triangle-Saturated Graphs

A graph \(G\) is \emph{triangle-saturated} if every possible edge insertion creates at least one new triangle. Furthermore, if no proper spanning subgraph has this property, then \(G\) is minimally triangle-saturated. (Minimally triangle-saturated graphs of order \(n\) are the diameter \(2\) critical graphs when \(n \geq 3\).) The maximally triangle-free graphs of order \(n\) are a proper subset of the minimally triangle-saturated graphs of order \(n\) when \(n \geq 6\).

All triangle-saturated graphs are easily derivable from the minimally triangle-saturated graphs which are primitive, that is, have no duplicate vertices. We determine the \(23\) minimally triangle-saturated graphs of orders \(n \leq 7\) and identify the \(6\) primitive graphs among them.