Graph-theory open problems

Geodesic cycles and Tutte's 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 open medium confidence

The problem, posed by Georgakopoulos and Sprüssel (2007), asks whether every $3$-connected finite graph admits an edge-length assignment $\ell$ such that every $\ell$-geodesic cycle is peripheral; a positive answer would yield a new proof of Tutte's theorem that peripheral cycles generate the cycle space. Web searches surfaced no verifiable post-2007 paper resolving the problem in either direction; the original GS paper (published 2009 in Electron. J. Combin.) explicitly leaves it open, and we found no follow-up announcing a proof, counterexample, or partial result on edge-length-induced geodesic-peripheral assignments.

Reviewer notes. The published version of the GS preprint (arXiv:0911.3999, Electron. J. Combin. 16 (2009) R144) predates the OPG posting only nominally (preprint 2007, OPG 2007-08-04) and therefore is not eligible as a post-posting citation. Hamann's 'Generating the cycle space of planar graphs' (arXiv:1411.6392) treats cycle-space generation in 3-connected planar graphs via Aut(G)-invariant nested cycles, but does not address edge-length-geodesic-vs-peripheral assignments. No counterexample or proof of the conjecture for finite 3-connected graphs was located. Confidence is medium because the niche topic could harbor results in less-indexed venues.

Auto-reviewed 2026-05-08 with claude-sonnet (subagent) (web search enabled).

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