Cactus Graph

A cactus graph, sometimes also called a cactus tree, a mixed Husimi tree, or a polygonal cactus with bridges, is a finite connected simple graph in which any two simple graph cycles have no edge in common. Equivalently, it is a connected graph in which any two (simple) cycles have at most one vertex in common. Equivalently, a cactus graph with at least two vertices is a connected graph in which every block is a cycle or an edge (White 2001, p. 57). The singleton graph is also a cactus graph. Every cactus graph is a planar graph.

Every cycle of a cactus graph has no cycle chord. However, there exist graphs (e.g., the theta₀-graph and Pasch graph) whose cycles all have no cycle chord but which are not cactus graphs.

The equality

where is the circuit rank and is the total number of simple undirected graph cycles holds for a connected graph iff it is a cactus graph (Volkmann 1996).

Every cactus graph is a unit-distance graph (Erdős et al. 1965, p. 121).

Every pseudotree is a cactus graph.

The numbers of unlabeled cactus graphs on 1, 2, ... nodes are 1, 1, 2, 4, 9, 23, 63, 188, ... (OEIS A000083).