teorema de los 2 factores

En la disciplina matemática de la teoría de grafos , el teorema del factor 2 , descubierto por Julius Petersen , es uno de los primeros trabajos en teoría de grafos. Se puede enunciar de la siguiente manera: ^{[ 1 ]}

Dejar${\displaystyle G}$sea ​​un grafo regular cuyo grado sea un número par,${\displaystyle 2k}$. Entonces los bordes de${\displaystyle G}$se puede dividir en${\displaystyle k}$2-factores disjuntos por aristas.

Aquí, un 2-factor es un subgrafo de${\displaystyle 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 primero demostró que un grafo 4-regular puede factorizarse en dos 2-factores tomando aristas alternas en un camino euleriano. Observó que la misma técnica utilizada para el grafo 4-regular produce una factorización de un${\displaystyle 2k}$-gráfico regular en dos${\displaystyle k}$-factores. ^{[ 2 ]}

Para demostrar este teorema, basta con considerar grafos conexos. Un grafo conexo de grado par tiene un camino euleriano. Recorrer este camino euleriano genera una orientación${\displaystyle D}$de${\displaystyle G}$de tal manera que cada punto tenga grado de entrada y grado de salida.${\displaystyle =k}$. A continuación, reemplace cada vértice${\displaystyle v\in V(D)}$por dos vértices${\displaystyle v'}$y${\displaystyle v''}$y reemplazar cada borde dirigido${\displaystyle uv}$del grafo orientado por una arista no dirigida desde${\displaystyle u'}$a${\displaystyle v''}$. Desde${\displaystyle D}$tiene grados de entrada y salida iguales a${\displaystyle k}$el grafo bipartito resultante${\displaystyle G'}$es${\displaystyle k}$-regular. Los bordes de${\displaystyle G'}$se puede dividir en${\displaystyle k}$emparejamientos perfectos según un teorema de Kőnig . Ahora fusionando${\displaystyle v'}$con${\displaystyle v''}$por cada${\displaystyle v}$recupera el gráfico${\displaystyle G}$y mapea el${\displaystyle k}$combinaciones perfectas de${\displaystyle G'}$sobre${\displaystyle k}$2-factores de${\displaystyle 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" alternativamente de rojo y azul las aristas de un camino o sendero, y luego usar las aristas de uno o ambos colores para la construcción de otros caminos o senderos. ^{[ 3 ]}

• Teorema de Petersen : todo grafo sin puentes 3-regular contiene un factor 2.