Төрт түсті теорема және үш қабырғалы графтар (Tört tüsti teorama jane üş qabyrğaly graftar)

3 regular graph with no 3 edge coloring
a term in graph theory

In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist. One of the equivalent forms of the four color theorem is that every snark is a non planar graph. Research on snarks originated in Peter G. Tait's work on the four color theorem in 1880, but their name is much newer, given to them by Martin Gardner in 1976. Beyond coloring, snarks also have connections to other hard problems in graph theory: writing in the Electronic Journal of Combinatorics, Miroslav Chladný and Martin Škoviera state that

As well as the problems they mention, W. T. Tutte's snark conjecture concerns the existence of Petersen graphs as graph minors of snarks; its proof has been long announced but remains unpublished, and would settle a special case of the existence of nowhere zero 4 flows.

The precise definition of snarks varies among authors, but generally refers to cubic graphs (having exactly three edges at each vertex) whose 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, 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. A 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 graphs, graphs without loops or multiple adjacencies. 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. 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. 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, and other authors have followed suit in forbidding these cycles. The requirement that a snark avoid cycles of length four or less can be summarized by stating that the girth of these graphs, the length of their shortest cycles, is at least five. More strongly, the definition used by 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. Although these definitions only consider constraints on the girth up to five, snarks with arbitrarily large girth exist.

Work by Peter G. Tait established that the four color theorem is true if and only if every snark is non planar. This theorem states that every planar graph has a graph coloring of its the vertices with four colors, but Tait showed how to convert 4 vertex colorings of maximal planar graphs into 3 edge colorings of their dual graphs, which are cubic and planar, and vice versa. A planar snark would therefore necessarily be dual to a counterexample to the four color theorem. Thus, the subsequent proof of the four color theorem also demonstrates that all snarks are non planar. All snarks are non Hamiltonian: when a cubic graph has a Hamiltonian cycle, it is always possible to 3 color its edges, by using two colors in alternation for the cycle, and the third color for the remaining edges. However, many known snarks are close to being Hamiltonian, in the sense that they are hypohamiltonian graphs: the removal of any single vertex leaves a Hamiltonian subgraph. A hypohamiltonian snark must be bicritical: the removal of any two vertices leaves a three edge colorable subgraph. The oddness of a cubic graph is defined as the minimum number of odd cycles, in any system of cycles that covers each vertex once (a 2 factor). For the same reason that they have no Hamiltonian cycles, snarks have positive oddness: a completely even 2 factor would lead to a 3 edge coloring, and vice versa. It is possible to construct infinite families of snarks whose oddness grows linearly with their numbers of vertices. The cycle double cover conjecture posits that in every bridgeless graph one can find a collection of cycles covering each edge twice, or equivalently that the graph can be embedded onto a surface in such a way that all faces of the embedding are simple cycles. When a cubic graph has a 3 edge coloring, it has a cycle double cover consisting of the cycles formed by each pair of colors. Therefore, among cubic graphs, the snarks are the only possible counterexamples. More generally, snarks form the difficult case for this conjecture: if it is true for snarks, it is true for all graphs. In this connection, Branko Grünbaum conjectured that no snark could be embedded onto a surface in such a way that all faces are simple cycles and such that every two faces either are disjoint or share only a single edge; if any snark had such an embedding, its faces would form a cycle double cover. However, a counterexample to Grünbaum's conjecture was found by Martin Kochol. Determining whether a given cyclically 5 connected cubic graph is 3 edge colorable is NP complete. Therefore, determining whether a graph is a snark is co NP complete.

W. T. Tutte conjectured that every snark has the Petersen graph as a minor. That is, he conjectured that the smallest snark, the Petersen graph, may be formed from any other snark by contracting some edges and deleting others. Equivalently (because the Petersen graph has maximum degree three) every snark has a subgraph that can be formed from the Petersen graph by subdividing some of its edges. This conjecture is a strengthened form of the four color theorem, because any graph containing the Petersen graph as a minor must be nonplanar. In 1999, Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas announced a proof of this conjecture. Steps towards this result have been published, but , the complete proof remains unpublished. See the Hadwiger conjecture for other problems and results relating graph coloring to graph minors. Tutte also conjectured a generalization to arbitrary graphs: every bridgeless graph with no Petersen minor has a nowhere zero 4 flow. That is, the edges of the graph may be assigned a direction, and a number from the set {1, 2, 3}, such that the sum of the incoming numbers minus the sum of the outgoing numbers at each vertex is divisible by four. As Tutte showed, for cubic graphs such an assignment exists if and only if the edges can be colored by three colors, so the conjecture would follow from the snark conjecture in this case. However, proving the snark conjecture would not settle the question of the existence of 4 flows for non cubic graphs.