Minimally triangle-saturated graphs: adjoining a single vertex

A graph G is triangle-saturated if every possible edge addition to G creates one or more new triangles (3-cycles). Such a graph is minimally triangle-saturated if removal of any edge from G leaves a graph that is not triangle-saturated. This paper investigates adding a single new vertex to a triangle-saturated graph so as to produce a new triangle-saturated graph, and determines the conditions under which the extended graph is minimally saturated. Particular attention is given to minimally saturated extensions which are primitive (no two vertices have the same neighbourhood). The results are applied to construct primitive maximal triangle-free graphs of every order n ≥ 9.