dedicated to professor w. t. tutte on the occasion of his eightieth birthday
An edge e of a minimally 3-connected graph G is non-essential if and only if the graph obtained by contracting e from G is both 3-connected and simple. Suppose that G is not a wheel. Tutte's Wheels Theorem states that G has at least one nonessential edge. We show that each longest cycle of G contains at least two nonessential edges. Moreover, each cycle of G whose edge set is not contained in a fan contains at least two non-essential edges. We characterize the minimally 3-connected graphs which contain a longest cycle containing exactly two non-essential edges.
1997 Academic Press
Tutte's Wheels Theorem [20] states that a minimally 3-connected graph G which is not a wheel contains an edge e such that the graph obtained from G by contracting e is both 3-connected and simple; that is G contains a non-essential edge. The existence of non-essential edges in a graph has proven to be an important induction tool in studying 3-connected graphs (see, for example, [20]). Hence it is worthwhile to study the distribution of these edges in a graph. In Theorem 1 we extend Tutte's Wheels Theorem by showing that every longest cycle of G contains at least two non-essential edges. Moreover, G has a longest cycle containing exactly two non-essential edges if and only if G is a member of one of five infinite families of graphs. We define fans below and also show that each cycle of G whose edge set is not contained in a fan contains at least two non-essential edges.
An edge of a 3-connected graph is said to be contractible if and only if the graph obtained from G by contracting e is 3-connected. There has been much interest in characterizing 3-connected graphs which have substructures such as longest cycles containing few contractible edges (see, for article no. TB961720 202 0095-8956Γ97 25.00