Null-homotopic graphs and triangle-completions of spanning trees

Abstract

We prove that a connected graph whose cycle space is generated by its triangles and which is planar or of maximum degree at most four has the property that it arises from an arbitrary spanning tree by iteratively adding edges which complete triangles.