Longest Paths in Polyhedral Graphs 

A finite graph G is called polyhedral iff it is isomorphic to the graph of vertices and edges of a 3-dimensional convex polyhedron. A graph-theoretic characterization of these graphs is given by a famous theorem due to E. Steinitz: polyhedral graphs coincide with 3-connected planar graphs. An old question concerning polyhedral graphs concerns the estimate for the minimum of the maximal length of a simple circuit in a polyhedral graph G with v = v(G) vertices. Denoting by h = h(G) the maximal length, Moon and Moser [MM] showed that h is at most c v^s where s = log 2 / log 3 = 0.630930 ... and c is a suitable constant. The graphs used to show this are easily constructed: Start with any triangle-faced polyhedron, and construct a sequence of polyhedra in which each member is obtained from the preceding one by attaching suitable shallow pyramids on all the faces. An easy calculation shows that the given estimate for s is best possible for all polyhedra in this sequence, regardless of the choice of the starting polyhedron.

One challenging open problem is to decide the validity of the following.

Conjecture: There exists a positive constant c such that every polyhedral graph with v vertices has a circuit of length at least c v^s with s = log 2 / log 3.

This is a modification of a conjecture posed explicitly in [GW], but probably conjectured by many other people as well. From private communications I know that some 20 years ago this problem attracted the attention of several rather clever people; no publication ensued since no worthwhile results were obtained.

The gap between the known and the conjectured is best seen from the fact that the existing estimates for the length of circuits involve log v rather than a power of v.

There is no clear indication what the largest c in the conjecture should be. An example shows that c < 2.203....

[[Note by Dan Archdeacon, I have heard that a paper by Z. Gao and X. Yu gives a path of length v^{.4}. F. Chung may have gotten v^{.5}, but that paper might have an error. I do not have these references.]]


[GW] B. Grunbaum and H. Walther, Shortness exponents of families of graphs, J. Combinat. Theory A 14 (1973) 364-385.

[MM] J.W. Moon and L. Moser, Simple paths on polyhedra, Pacific J. Math. 13 (1963) 629-631.

Submitted by: Branko Grunbaum

Send comments to dan.archdeacon@uvm.edu and to grunbaum@math.washington.edu

August, 1995