En la disciplina matemática de la teoría de grafos , el teorema de los dos factores , descubierto por Julius Petersen , es uno de los primeros trabajos en teoría de grafos. Puede enunciarse de la siguiente manera: [1]
Sea G un grafo regular cuyo grado es un número par, 2 k . Entonces las aristas de G se pueden dividir en k 2-factores disjuntos entre sí.
Aquí, un factor 2 es un subgrafo de G en el que todos los vértices tienen grado dos; es decir, es una colección de ciclos que juntos tocan cada vértice exactamente una vez.
Para demostrar esta forma generalizada del teorema, Petersen demostró primero que un grafo 4-regular puede factorizarse en dos 2-factores tomando aristas alternadas en un camino euleriano. Observó que la misma técnica utilizada para el grafo 4-regular produce una factorización de un grafo 2k - regular en dos k -factores. [2]
Para demostrar este teorema, es suficiente considerar grafos conexos. Un grafo conexo con grado par tiene un sendero euleriano. Recorrer este sendero euleriano genera una orientación D de G tal que cada punto tiene grado de entrada y grado de salida = k . A continuación, reemplace cada vértice v ϵ V ( D ) por dos vértices v' y v” , y reemplace cada arista dirigida uv del grafo orientado por una arista no dirigida de u' a v” . Como D tiene grados de entrada y salida iguales a k, el grafo bipartito resultante G' es k -regular. Las aristas de G' se pueden dividir en k emparejamientos perfectos por un teorema de Kőnig . Ahora, fusionando v' con v” para cada v , se recupera el grafo G y se asignan los k emparejamientos perfectos de G' a k 2-factores de G que dividen sus aristas. [1]
El teorema fue descubierto por Julius Petersen , un matemático danés. Es uno de los primeros resultados descubiertos en el campo de la teoría de grafos . El teorema aparece por primera vez en el artículo de 1891 "Die Theorie der regulären graphs" . Para demostrar el teorema, la idea fundamental de Petersen fue "colorear" los bordes de un sendero o un camino alternativamente de rojo y azul, y luego usar los bordes de uno o ambos colores para la construcción de otros caminos o ensayos. [3]