A longest cycle version of Tutte's wheels theorem (Q1369899)

From MaRDI portal
scientific article
Language Label Description Also known as
English
A longest cycle version of Tutte's wheels theorem
scientific article

    Statements

    A longest cycle version of Tutte's wheels theorem (English)
    0 references
    0 references
    0 references
    22 February 1998
    0 references
    Let \(G\) be a minimally 3-connected graph. An edge \(e\) of \(G\) is non-essential if its contraction yields a 3-connected graph that is simple. Tutte showed that any minimally 3-connected graph which is not a wheel has at least one non-essential edge. Here it is shown that in fact each longest cycle of such a non-wheel contains at least two non-essential edges. Indeed, each cycle whose edges are not part of a fan has the same property. Furthermore, a non-wheel has a longest cycle containing exactly two non-essential edges if and only if it is one of five types of graphs derived from fans or wheels.
    0 references
    3-connected graph
    0 references
    non-essential edge
    0 references
    longest cycle
    0 references

    Identifiers