A Longest Cycle Version of Tutte's Wheels Theorem

AbstractAn edgeeof a minimally 3-connected graphGis non-essential if and only if the graph obtained by contractingefromGis both 3-connected and simple. Suppose thatGis not a wheel. Tutte's Wheels Theorem states thatGhas at least one non-essential edge. We show that each longest cycle ofGcontains at least two non-essential edges. Moreover, each cycle ofGwhose 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