Geodesic cycles and Tutte's Theorem

OPG_3_connected_geodesic_cycles_peripheral_lengths

Source: Open Problem Garden: geodesic_cycles_and_tuttes_theorem

Medium ★★ Graph Theory » Basic Graph Theory » Cycles accessible to undergrads

Authors: Georgakopoulos, Agelos, Sprüssel, Philipp— posted by Agelos on 2007-08-04

Status ai-disproved high confidence

The eight-vertex graph obtained by inserting a degree-three vertex into every face of a tetrahedron is a counterexample.

Auto-reviewed 2026-09-16 with gpt-6-astra.

AI-generated write-up ai-disproved

Open the PDF write-up

This is a model-generated research artifact, not a peer-reviewed publication or a formally verified proof.

Problem. If $ G $ is a $ 3 $ -connected finite graph, is there an assignment of lengths $ \ell: E(G) \to \mathb R^+ $ to the edges of $ G $ , such that every $ \ell $ -geodesic cycle is peripheral ?

Keywords: cycle space · geodesic cycles · peripheral cycles

Discussion

A cycle $ C $ is $ \ell $ -geodesic if for every two vertices $ x,y $ on $ C $ there is no $ x $ - $ y $ ~path in $ G $ shorter, with respect to $ \ell $ , than both $ x $ - $ y $ ~arcs on $ C $ . It is not hard to prove [GS] that for every finite graph $ G $ and every assignment of edge lengths $ \ell: E(G) \to \mathb R^+ $ the $ \ell $ -geodesic cycles of $ G $ generate its cycle space. Thus, a positive answer to the problem would imply a new proof of Tutte's classical theorem [T] that the peripheral cycles of a $ 3 $ -connected finite graph generate its cycle space.

Bibliography

★ [GS] Angelos Georgakopoulos, Philipp Sprüssel: Geodesic topological cycles in locally finite graphs . Preprint 2007. Geodesic topological cycles in locally finite graphs
[T] W.T. Tutte, How to draw a graph. Proc. London Math. Soc. 13 (1963), 743–768.