Cycles through four edges in 3-connected cubic graphs (Q753835): Difference between revisions

The authors define a path system in a graph to be a subgraph consisting of pairwise disjoint paths. Such a path system is said to be free if it contains no cutset of odd cardinality. A necessary and sufficient condition is given for the existence, in a 3-connected cubic graph, of a circuit containing a given free path system of size at most 4. This condition is expressed in terms of contractions of the given graph to certain forbidden configurations. It has been shown by Häggvist and Thomassen that in a \((k+1)\)-connected graph any k independent edges lie on a circuit. It has been conjectured by Holton and Thomassen that this is also true for any cyclically \((k+1)\)-edge-connected cubic graph. A corollary to the theorem of this paper is the verification of that conjecture for \(k=4\).