En la disciplina matemática de la teoría de grafos , el teorema de 2 factores , descubierto por Julius Petersen , es uno de los primeros trabajos en teoría de grafos. Puede expresarse de la siguiente manera:
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 probar esta forma generalizada del teorema, Petersen primero demostró que un gráfico de 4 regulares se puede factorizar en dos 2 factores tomando aristas alternas en un camino euleriano. Señaló que la misma técnica utilizada para el gráfico regular de 4 produce una factorización de un gráfico regular de 2 k en dos factores k . [2]
Para probar este teorema, es suficiente considerar gráficas conectadas. Un gráfico conectado con un grado par tiene un rastro euleriano. Atravesar este rastro euleriano genera una orientación D de G tal que cada punto tiene un grado y un grado superior = k . Luego, reemplace cada vértice v ϵ V ( D ) por dos vértices v ' y v ” , y reemplace cada borde dirigido uv del gráfico orientado por un borde no dirigido de u' a v” . Dado que D tiene grados de entrada y salida iguales a k, el gráfico bipartito resultante G ' es k -regular. Los bordes de G ' se pueden dividir en k emparejamientos perfectos mediante un teorema de Kőnig . Ahora, fusionando v ' con v ” para cada v, recupere el gráfico G y mapee las k coincidencias perfectas de G' en k 2 factores de G que dividen sus bordes. [1]
El teorema fue descubierto por Julius Petersen , un matemático danés. De hecho, es uno de los primeros resultados de la teoría de grafos . El teorema aparece primero en el artículo de 1891 "Die Theorie der regulären graphs" . Para probar el teorema, la idea fundamental de Petersen era "colorear" los bordes de una prueba o un camino alternativamente rojo y azul, y luego usar los bordes de uno o ambos colores para la construcción de otros caminos o pruebas. [3]