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 con coincidencias perfectas . Es una generalización del teorema del matrimonio de Hall de grafos bipartitos a grafos arbitrarios. [ aclaración necesaria ] Es un caso especial de la fórmula de Tutte-Berge .
Nuestro objetivo es caracterizar todos los gráficos que no tienen una coincidencia perfecta. Comencemos con el caso más obvio de un grafo sin coincidencia perfecta: un grafo con un número impar de vértices. En tal gráfico, cualquier coincidencia deja al menos un vértice no coincidente, por lo que no puede ser perfecto.
Un caso un poco más general es un gráfico 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 tales componentes componentes impares . En cualquier coincidencia, cada vértice solo puede coincidir con vértices en el mismo componente. Por lo tanto, cualquier emparejamiento deja al menos un vértice sin emparejar en cada componente impar, por lo que no puede ser perfecto.
A continuación, considere un gráfico G con un vértice u tal que, si eliminamos de G el vértice u y sus bordes adyacentes, el gráfico restante (denotado G − u ) tiene dos o más componentes impares. Como arriba, 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 dado que hay dos o más vértices no emparejados, y solo uno de ellos puede coincidir con u , al menos otro vértice permanece sin emparejar, por lo que la coincidencia no es perfecta.
Finalmente, considere un grafo G con un conjunto de vértices U tales 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 | tu | componentes impares. Como se explicó anteriormente, cualquier coincidencia deja al menos un vértice no coincidente en cada componente impar, y estos pueden coincidir solo con los vértices de U , pero no hay suficientes vértices en U para todos estos vértices no coincidentes, por lo que la coincidencia no es perfecta.
Hemos llegado a una condición necesaria : si G tiene una coincidencia perfecta, entonces para cada subconjunto de vértices U en G , el grafo G − U tiene como máximo | tu | componentes impares.