Irreducible snarks of given order and cyclic connectivity Original Research Article

A snark is a “nontrivial” cubic graph whose edges cannot be properly coloured by three colours; it is irreducible if each nontrivial edge-cut divides the snark into colourable components. Irreducible snarks can be viewed as simplest uncolourable structures. In fact, all snarks can be composed from irreducible snarks in a suitable way. In this paper we deal with the problem of the existence of irreducible snarks of given order and cyclic connectivity. We determine all integers n for which there exists an irreducible snark of order n, and construct irreducible snarks with cyclic connectivity 4 and 5 of all possible orders. Moreover, we construct cyclically 6-connected irreducible snarks of each even order image. (Cyclically 7-connected snarks are believed not to exist.)