We investigate some properties of graphs whose cycle space has a basis constituted of triangles ('null-homotopic' graphs). We obtain characterizations in the case of planar graphs, and more generally, of graphs not contractible onto Ks. These characterizations involve separating subsets and decompositions into triangulations of discs.
The notion of homotopy in graphs was introduced by the authors [3]. Another notion of homotopy in graphs has been considered by Quilliot [4].
Cycles in graphs are viewed algebraically, i.e., they are considered as vectors in GF(2) e, where E is the edge-set of the graph. We say that two cycles C and C' are homotopic in a graph G = (V, E) if there are triangles T~ (i = 1,..., k) such that C = C' + E~=I T~.
The relationship between the null-homotopy property (i.e., 'any two cycles are homotopic') and properties relative to connectedness have been considered in the context of topological spaces (see Whyburn [6, chap. XI] for details). Inspired by these concepts we investigate in the present paper some properties of graphs of a similar flavour. We mention that the graph properties we obtain are not reducible to topological properties.
In the case of graphs not contractible onto K5, we prove in Section 3 the equivalence between the null-homotopy property and the property that any two induced subgraphs whose union is the whole graph have a connected intersection. This last property is characterized in two ways in Section 1. The equivalence is not true in general (Section 2).