# Triangle-free and Triangle-saturated Graphs

MacDougall, James A. and Eggleton, Roger B. (1997) Triangle-free and Triangle-saturated Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 25 . pp. 3-21.

 Preview
PDF - Accepted Version
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.