Triangle-free and Triangle-saturated Graphs
James A. MacDougall, Roger B. Eggleton · 1997
A graph $G$ is {\em 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 {\em minimally triangle-saturated}. (Minimally triangle-saturated graphs of order at least 3 are the diameter 2 critical graphs.) 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 {\em 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.