# Snark (teoría de grafos)

En el campo matemático de la teoría de grafos, un snark es un grafo no dirigido con exactamente tres aristas por vértice cuyas aristas no pueden colorearse con sólo tres colores. Para evitar casos triviales, los snarks suelen tener requisitos adicionales en cuanto a su conectividad y a la longitud de sus ciclos. Existen infinitos snarks.
Una de las formas equivalentes del teorema de los cuatro colores es que cada snark es un grafo no plano. La investigación sobre los snarks tiene su origen en los trabajos de Peter G. Tait sobre el teorema de los cuatro colores en 1880, pero su nombre es mucho más reciente, ya que se lo dio Martin Gardner en 1976. Más allá de la coloración, los snarks también están relacionados con otros problemas difíciles de la teoría de grafos: en el Electronic Journal of Combinatorics, Miroslav Chladný y Martin Škoviera afirman que:
   En el estudio de varios problemas importantes y difíciles de la teoría de grafos (como la conjetura del ciclo doble tapa y la conjetura de los 5 flujos en flujo cero en ninguna parte (nowhere-zero flow), uno se encuentra con una interesante pero algo misteriosa variedad de grafos llamados snarks. A pesar de su sencilla definición... y de más de un siglo de investigación, sus propiedades y estructura son en gran parte desconocidas.
Además de los problemas que mencionan, la conjetura snark de W. T. Tutte se refiere a la existencia de grafos de Petersen como grafos menores de snarks; su demostración se ha anunciado hace tiempo pero sigue sin publicarse, y resolvería un caso especial de la existencia de 4-flujos en flujo cero en ninguna parte.

## Historia y ejemplos

Los snarks fueron bautizados así por el matemático estadounidense Martin Gardner en 1976, en honor al misterioso y escurridizo objeto del poema La caza del Snark de Lewis Carroll. Sin embargo, el estudio de esta clase de grafos es bastante más antiguo que su nombre. Peter G. Tait inició el estudio de los snarks en 1880, cuando demostró que el teorema de los cuatro colores es equivalente a la afirmación de que ningún snark es plano. El primer gráfico conocido como snark fue el gráfico de Petersen; Julius Petersen demostró que era un snark en 1898, aunque Alfred Kempe ya lo había estudiado con un propósito diferente en 1886.
Los siguientes cuatro snarks conocidos fueron:
* los snarks de Blanuša (dos con 18 vértices), descubiertos por Danilo Blanuša en 1946,
* el snark Descartes (210 vértices), descubierto por Bill Tutte en 1948, y
* el snark Szekeres (50 vértices), descubierto por George Szekeres en 1973.
En 1975, Rufus Isaacs generalizó el método de Blanuša para construir dos familias infinitas de snarks: los snarks flor y los snarks Blanuša-Descartes-Szekeres, una familia que incluye los dos snarks de Blanuša, el snark Descartes y el snark Szekeres. Isaacs también descubrió un snark de 30 vértices que no pertenece a la familia Blanuša-Descartes-Szekeres y que no es un snark de flor: el snark de doble estrella. En 1989 se descubrió el snark de 50 vértices de Watkins.
Otro notable grafo cúbico no coloreable con tres aristas es el grafo de Tietze, con 12 vértices; como descubrió Heinrich Franz Friedrich Tietze en 1910, forma el límite de una subdivisión de la banda de Möbius que requiere seis colores. Sin embargo, debido a que contiene un triángulo, generalmente no se considera un snark. Según las definiciones estrictas de snarks, los snarks más pequeños son el grafo de Petersen y los snarks de Blanuša, seguidos de seis snarks diferentes de 20 vértices.
Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund y Klas Markström generaron en 2012 una lista de todos los snarks de hasta 36 vértices (según una definición estricta) y de hasta 34 vértices (según una definición más débil). El número de snarks para un número par de vértices dado crece al menos exponencialmente en el número de vértices. Dado que tienen vértices de grado impar, todos los snarks deben tener un número par de vértices por el lema del apretón de manos). La secuencia A130315 de la OEIS contiene el número de snarks no triviales de $2n$ vértices para valores pequeños de $n$.

## Definición

La definición precisa de snarks varía según los autores, pero generalmente se refiere a grafos cúbicos (que tienen exactamente tres aristas en cada vértice) cuyas aristas no pueden colorearse con sólo tres colores. Según el teorema de Vizing, el número de colores necesarios para las aristas de un grafo cúbico es tres (grafos de «clase uno») o cuatro (grafos de «clase dos»), por lo que los snarks son grafos cúbicos de clase dos. Sin embargo, para evitar casos en los que un snark es de clase dos por razones triviales, o se construye de forma trivial a partir de grafos más pequeños, a menudo se imponen restricciones adicionales sobre la conectividad y la longitud de los ciclos. En particular:
* Si un grafo cúbico tiene un puente, una arista cuya eliminación lo desconectaría, entonces no puede ser de clase uno. Por el lema del apretón de manos, los subgrafos a ambos lados del puente tienen un número impar de vértices cada uno. Cualquiera que sea el color elegido para el puente, su número impar de vértices impide que estos subgrafos estén cubiertos por ciclos que alternan entre los otros dos colores, como sería necesario en una coloración de 3 aristas. Por esta razón, generalmente se requiere que los snarks no tengan puentes.
* Un bucle (una arista que conecta un vértice consigo misma) no puede colorearse sin que el mismo color aparezca dos veces en ese vértice, lo que supone una violación de los requisitos habituales para la coloración de aristas de grafos. Además, un ciclo formado por dos vértices conectados por dos aristas siempre puede sustituirse por una única arista que conecte a sus otros dos vecinos, lo que simplifica el grafo sin cambiar su coloreabilidad de tres aristas. Por estas razones, los snarks se limitan generalmente a grafos simples, sin bucles ni adyacencias múltiples.
* Si un grafo contiene un triángulo, puede simplificarse de nuevo sin cambiar su coloreabilidad en tres aristas, contrayendo los tres vértices del triángulo en un único vértice. Por lo tanto, muchas definiciones de snarks prohíben los triángulos. Sin embargo, aunque este requisito también se estableció en el trabajo de Gardner que dio el nombre de «snark» a estos grafos, Gardner incluye el grafo de Tietze, que contiene un triángulo, como un snark.
* Si un grafo contiene un ciclo de cuatro vértices, puede simplificarse de dos maneras diferentes eliminando dos aristas opuestas del ciclo y sustituyendo los caminos resultantes de vértices de grado dos por aristas simples. Tiene una coloración de tres aristas si y sólo si al menos una de estas simplificaciones la tiene. Por lo tanto, Isaacs requiere que un grafo cúbico «no trivial» de clase dos evite ciclos de cuatro vértices, y otros autores han seguido su ejemplo prohibiendo estos ciclos. El requisito de que un snark evite ciclos de longitud cuatro o menos puede resumirse afirmando que la circunferencia de estos grafos, la longitud de sus ciclos más cortos, es al menos cinco.
* En concreto, la definición utilizada por Brinkmann et al. (2012) exige que los snarks estén conectados cíclicamente por 4 aristas. Esto significa que no puede haber ningún subconjunto de tres o menos aristas cuya eliminación desconectaría el grafo en dos subgrafos, cada uno de los cuales tiene al menos un ciclo. Brinkmann et al. definen un snark como un grafo cúbico y cíclicamente conectado por 4 aristas de circunferencia cinco o más y clase dos; definen un «snark débil» para permitir circunferencia cuatro.
Aunque estas definiciones sólo consideran restricciones en la circunferencia hasta cinco, existen snarks con circunferencias arbitrariamente grandes.

## Propiedades

El trabajo de Peter G. Tait estableció que el teorema de los cuatro colores es cierto si y sólo si cada snark no es planar. Este teorema establece que cada grafo planar tiene una coloración de sus vértices con cuatro colores, pero Tait demostró cómo convertir coloraciones de 4 vértices de grafos planares máximos en coloraciones de 3 aristas de sus grafos duales, que son cúbicos y planares, y viceversa. Por tanto, un snark plano sería necesariamente dual a un contraejemplo del teorema de los cuatro colores. Así, la prueba posterior del teorema de los cuatro colores también demuestra que todos los snarks no son planares.
Todos los snarks son no hamiltonianos: cuando un grafo cúbico tiene un ciclo hamiltoniano, siempre es posible colorear sus aristas en 3 colores, utilizando dos colores en alternancia para el ciclo, y el tercer color para las aristas restantes. Sin embargo, muchos snarks conocidos están cerca de ser hamiltonianos, en el sentido de que son grafos hipohamiltonianos: la eliminación de cualquier vértice deja un subgrafo hamiltoniano. Un snark hipohamiltoniano debe ser bicrítico: la eliminación de dos vértices cualesquiera deja un subgrafo de tres aristas coloreables. La imparidad de un grafo cúbico se define como el número mínimo de ciclos impares, en cualquier sistema de ciclos que cubra cada vértice una vez (un factor 2). Por la misma razón por la que no tienen ciclos hamiltonianos, los snarks tienen imparidad positiva: un 2-factor completamente par llevaría a una coloración de 3 aristas, y viceversa. Es posible construir infinitas familias de snarks cuya imparidad crece linealmente con su número de vértices.
La conjetura de la doble cubierta de ciclos postula que en todo grafo sin puentes se puede encontrar una colección de ciclos que cubren dos veces cada arista, o lo que es lo mismo, que el grafo se puede incrustar en una superficie de forma que todas las caras de la incrustación sean ciclos simples. Cuando un grafo cúbico tiene una coloración de 3 aristas, tiene una doble cobertura de ciclos formada por los ciclos formados por cada par de colores. Por lo tanto, entre los grafos cúbicos, los snarks son los únicos contraejemplos posibles. De forma más general, los snarks constituyen el caso difícil de esta conjetura: si es cierta para los snarks, lo es para todos los grafos. En este sentido, Branko Grünbaum conjeturó que ningún snark podría incrustarse en una superficie de forma que todas las caras fueran ciclos simples y que cada dos caras fueran disjuntas o compartieran una única arista; si algún snark tuviera tal incrustación, sus caras formarían una doble cubierta de ciclos. Sin embargo, Martin Kochol encontró un contraejemplo a la conjetura de Grünbaum.
Determinar si un grafo cúbico de 5 conexiones cíclicas es coloreable por 3 aristas es NP-completo. Por lo tanto, determinar si un grafo es un snark es co-NP-completo.

## Conjetura Snark

W. T. Tutte conjeturó que cada snark tiene el grafo de Petersen como menor. Es decir, conjeturó que el snark más pequeño, el grafo de Petersen, puede formarse a partir de cualquier otro snark contrayendo algunas aristas y eliminando otras. De forma equivalente (ya que el grafo de Petersen tiene un grado máximo de tres), cada snark tiene un subgrafo que puede formarse a partir del grafo de Petersen subdividiendo algunas de sus aristas. Esta conjetura es una forma reforzada del teorema de los cuatro colores, porque cualquier grafo que contenga el grafo de Petersen como menor debe ser no plano. En 1999, Neil Robertson, Daniel P. Sanders, Paul Seymour, y Robin Thomas anunciaron una prueba de esta conjetura. Pasos hacia este resultado se han publicado en 2016 y 2019, pero la prueba completa sigue sin publicarse. Véase la conjetura de Hadwiger para otros problemas y resultados relacionados con la coloración de grafos y grafos menores.
Tutte también conjeturó una generalización para grafos arbitrarios: todo grafo sin puentes y sin Petersen menor tiene un 4-flujos en cero en ninguna parte . Es decir, a las aristas del grafo se les puede asignar una dirección y un número del conjunto {1, 2, 3}, tal que la suma de los números entrantes menos la suma de los números salientes en cada vértice sea divisible por cuatro. Como demostró Tutte, para grafos cúbicos existe tal asignación si y sólo si las aristas se pueden colorear con tres colores, por lo que la conjetura se derivaría de la conjetura snark en este caso. Sin embargo, demostrar la conjetura snark no resolvería la cuestión de la existencia de flujos de 4 para grafos no cúbicos.