Editing Snark (graph theory) (section)

==Definition==
The precise definition of snarks varies among authors,{{r|bghm|isaacs}} but generally refers to [[cubic graphs]] (having exactly three edges at each vertex) whose [[edge coloring|edges cannot be colored]] with only three colors. By [[Vizing's theorem]], the number of colors needed for the edges of a cubic graph is either three ("class one" graphs) or four ("class two" graphs), so snarks are cubic graphs of class two. However, in order to avoid cases where a snark is of class two for trivial reasons, or is constructed in a trivial way from smaller graphs, additional restrictions on connectivity and cycle lengths are often imposed. In particular:
*If a cubic graph has a [[Bridge (graph theory)|bridge]], an edge whose removal would disconnect it, then it cannot be of class one. By the [[handshaking lemma]], the subgraphs on either side of the bridge have an odd number of vertices each. Whichever of three colors is chosen for the bridge, their odd number of vertices prevents these subgraphs from being covered by cycles that alternate between the other two colors, as would be necessary in a 3-edge-coloring. For this reason, snarks are generally required to be bridgeless.{{r|gardner|isaacs}}
*A [[Loop (graph theory)|loop]] (an edge connecting a vertex to itself) cannot be colored without causing the same color to appear twice at that vertex, a violation of the usual requirements for graph edge coloring. Additionally, a cycle consisting of two vertices connected by two edges can always be replaced by a single edge connecting their two other neighbors, simplifying the graph without changing its three-edge-colorability. For these reasons, snarks are generally restricted to [[simple graph]]s, graphs without loops or multiple adjacencies.{{r|isaacs}}
*If a graph contains a triangle, then it can again be simplified without changing its three-edge-colorability, by contracting the three vertices of the triangle into a single vertex. Therefore, many definitions of snarks forbid triangles.{{r|isaacs}} However, although this requirement was also stated in Gardner's work giving the name "snark" to these graphs, Gardner lists [[Tietze's graph]], which contains a triangle, as being a snark.{{r|gardner}}
*If a graph contains a four-vertex cycle, it can be simplified in two different ways by removing two opposite edges of the cycle and replacing the resulting paths of degree-two vertices by single edges. It has a three-edge-coloring if and only if at least one of these simplifications does. Therefore, Isaacs requires a "nontrivial" cubic class-two graph to avoid four-vertex cycles,{{r|isaacs}} and other authors have followed suit in forbidding these cycles.{{r|bghm}} The requirement that a snark avoid cycles of length four or less can be summarized by stating that the [[Girth (graph theory)|girth]] of these graphs, the length of their shortest cycles, is at least five.
*More strongly, the definition used by {{harvtxt|Brinkmann|Goedgebeur|Hägglund|Markström|2012}} requires snarks to be cyclically 4-edge-connected. That means there can be no subset of three or fewer edges, the removal of which would disconnect the graph into two subgraphs each of which has at least one cycle. Brinkmann et al. define a snark to be a cubic and cyclically 4-edge-connected graph of girth five or more and class two; they define a "weak snark" to allow girth four.{{r|bghm}}
Although these definitions only consider constraints on the girth up to five, snarks with arbitrarily large girth exist.{{r|kochol1996}}