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
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
0 references