In a 3‐connected planar triangulation, every circuit of length ≥ 4 divides the rest of the edges into two nontrivial parts (inside and outside) which are “separated” by the circuit. Neil Robertson asked to what extent triangulations are characterized by this property, and conjectured an answer. In this paper we prove his conjecture, that if G is simple and 3‐connected and every circuit of length ≥ 4 has at least two “bridges,” then G may be built up by “clique‐sums” starting from complete graphs and planar triangulations. This is a generalization of Dirac's theorem about chordal graphs.
All Science Journal Classification (ASJC) codes
- Geometry and Topology