En la disciplina matemática de la teoría de grafos , el teorema de Tutte , llamado así por William Thomas Tutte , es una caracterización de grafos finitos no dirigidos con emparejamientos perfectos . Es un caso especial de la fórmula de Tutte-Berge .
El objetivo es caracterizar todos los grafos que no tienen una correspondencia perfecta. Empecemos por el caso más obvio de un grafo sin correspondencia perfecta: un grafo con un número impar de vértices. En un grafo de este tipo, cualquier correspondencia deja al menos un vértice sin correspondencia, por lo que no puede ser perfecto.
Un caso un poco más general es un grafo desconectado en el que uno o más componentes tienen un número impar de vértices (incluso si el número total de vértices es par). Llamemos a estos componentes componentes impares . En cualquier coincidencia, cada vértice solo puede coincidir con vértices del mismo componente. Por lo tanto, cualquier coincidencia deja al menos un vértice sin coincidir en cada componente impar, por lo que no puede ser perfecta.
A continuación, considere un grafo G con un vértice u tal que, si eliminamos de G el vértice u y sus aristas adyacentes, el grafo restante (denotado G − u ) tiene dos o más componentes impares. Como antes, cualquier coincidencia deja, en cada componente impar, al menos un vértice que no coincide con otros vértices en el mismo componente. Tal vértice solo puede coincidir con u . Pero como hay dos o más vértices no coincidentes, y solo uno de ellos puede coincidir con u , al menos otro vértice permanece sin coincidir, por lo que la coincidencia no es perfecta.
Por último, considere un grafo G con un conjunto de vértices U tal que, si eliminamos de G los vértices en U y todas las aristas adyacentes a ellos, el grafo restante (denotado G − U ) tiene más de | U | componentes impares. Como se explicó anteriormente, cualquier coincidencia deja al menos un vértice sin coincidir en cada componente impar, y estos solo se pueden coincidir con vértices de U , pero no hay suficientes vértices en U para todos estos vértices sin coincidir, por lo que la coincidencia no es perfecta.
Hemos llegado a una condición necesaria : si G tiene un emparejamiento perfecto, entonces para cada subconjunto de vértices U en G , el grafo G − U tiene como máximo | U | componentes impares. El teorema de Tutte dice que esta condición es necesaria y suficiente para la existencia de un emparejamiento perfecto.
Un grafo, G = ( V , E ) , tiene una correspondencia perfecta si y solo si para cada subconjunto U de V , el subgrafo G − U tiene como máximo | U | componentes impares ( componentes conexos que tienen un número impar de vértices ). [1]
Primero escribimos la condición:
donde denota el número de componentes impares del subgrafo inducido por .
Necesidad de (∗): Esta dirección ya se discutió en la sección Intuición más abajo, pero resumamos aquí la prueba. Consideremos un grafo G , con un emparejamiento perfecto. Sea U un subconjunto arbitrario de V . Borremos U . Sea C un componente impar arbitrario en G − U . Como G tuvo un emparejamiento perfecto, al menos un vértice en C debe coincidir con un vértice en U . Por lo tanto, cada componente impar tiene al menos un vértice coincidente con un vértice en U . Como cada vértice en U puede estar en esta relación con a lo sumo un componente conexo (debido a que coincide a lo sumo una vez en un emparejamiento perfecto), impar ( G − U ) ≤ | U | . [2]
Suficiencia de (∗): Sea G un grafo arbitrario sin correspondencia perfecta. Encontraremos un llamado violador de Tutte , es decir, un subconjunto S de V tal que | S | < odd ( G − S ) . Podemos suponer que G es maximizador de aristas, es decir, G + e tiene una correspondencia perfecta para cada arista e no presente en G ya. De hecho, si encontramos un violador de Tutte S en el grafo maximizador de aristas G , entonces S también es un violador de Tutte en cada subgrafo generador de G , ya que cada componente impar de G − S se dividirá en posiblemente más componentes, al menos uno de los cuales nuevamente será impar.
Definimos S como el conjunto de vértices con grado | V | − 1 . Primero consideramos el caso donde todos los componentes de G − S son grafos completos. Entonces S tiene que ser un violador de Tutte, ya que si impar ( G − S ) ≤ | S | , entonces podríamos encontrar una correspondencia perfecta haciendo coincidir un vértice de cada componente impar con un vértice de S y emparejando todos los demás vértices (esto funcionará a menos que | V | sea impar, pero entonces ∅ es un violador de Tutte).
Ahora supongamos que K es un componente de G − S y x , y ∈ K son vértices tales que xy ∉ E . Sean x , a , b ∈ K los primeros vértices en un camino x , y más corto en K . Esto asegura que xa , ab ∈ E y xb ∉ E . Como a ∉ S , existe un vértice c tal que ac ∉ E . A partir de la maximalidad de aristas de G , definimos M 1 como una coincidencia perfecta en G + xb y M 2 como una coincidencia perfecta en G + ac . Observe que seguramente xb ∈ M 1 y ac ∈ M 2 .
Sea P el camino máximo en G que comienza en c con una arista de M 1 y cuyas aristas se alternan entre M 1 y M 2 . ¿Cómo puede terminar P ? A menos que lleguemos a un vértice 'especial' como x , a o b , siempre podemos continuar: c es M 2 -emparejado por ca , por lo que la primera arista de P no está en M 2 , por lo tanto, el segundo vértice es M 2 -emparejado por una arista diferente y continuamos de esta manera.
Sea v el último vértice de P . Si la última arista de P está en M 1 , entonces v tiene que ser a , ya que de lo contrario podríamos continuar con una arista desde M 2 (incluso para llegar a x o b ). En este caso definimos C := P + ac . Si la última arista de P está en M 2 , entonces seguramente v ∈ { x , b } por una razón análoga y definimos C := P + va + ac .
Ahora C es un ciclo en G + ac de longitud par con todas las demás aristas en M 2 . Ahora podemos definir M := M 2 Δ C (donde Δ es diferencia simétrica ) y obtenemos una correspondencia perfecta en G , una contradicción.
La fórmula de Tutte–Berge dice que el tamaño de una coincidencia máxima de un grafo es igual a . De manera equivalente, la cantidad de vértices no coincidentes en una coincidencia máxima es igual a .
Esta fórmula se desprende del teorema de Tutte, junto con la observación de que tiene una correspondencia de tamaño si y solo si el grafo obtenido añadiendo nuevos vértices, cada uno unido a cada vértice original de , tiene una correspondencia perfecta. Como cualquier conjunto que se separa en más de componentes debe contener todos los nuevos vértices, (*) se satisface para si y solo si .
Para los grafos infinitos conexos que son localmente finitos (cada vértice tiene grado finito), se cumple una generalización de la condición de Tutte: dichos grafos tienen correspondencias perfectas si y sólo si no hay un subconjunto finito, cuya eliminación crea un número de componentes impares finitos mayor que el tamaño del subconjunto. [3]
