Triangle-Free and Triangle-Saturated Graphs

Abstract

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\ge 3$.) The maximally triangle-free graphs of order $n$ are a proper subset of the minimally triangle-saturated graphs of order $n$ when $n\ge 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\le 7$ and identify the $6$ primitive graphs among them.