En matemáticas, el teorema de Veblen , introducido por Oswald Veblen ( 1912 ), establece que el conjunto de aristas de un grafo finito puede escribirse como una unión de ciclos simples disjuntos si y solo si cada vértice tiene un grado par. Por lo tanto, está estrechamente relacionado con el teorema de Euler (1736) de que un gráfico finito tiene un recorrido de Euler (un ciclo único no simple que cubre los bordes del gráfico) si y solo si está conectadoy cada vértice tiene un grado uniforme. De hecho, se puede obtener una representación de un gráfico como una unión de ciclos simples a partir de un recorrido de Euler dividiendo repetidamente el recorrido en ciclos más pequeños siempre que haya un vértice repetido. Sin embargo, el teorema de Veblen se aplica también a gráficos desconectados y puede generalizarse a gráficos infinitos en los que cada vértice tiene un grado finito ( Sabidussi 1964 ).
Si un grafo infinito numerable G no tiene vértices de grado impar, entonces puede escribirse como una unión de ciclos simples disjuntos (finitos) si y solo si cada subgrafo finito de G puede extenderse (agregando más aristas y vértices de G ) a un grafo euleriano finito. En particular, cada grafo numerablemente infinito con un solo extremo y sin vértices impares puede escribirse como una unión de ciclos disjuntos ( Sabidussi 1964 ).
Ver también
Referencias
- Euler, L. (1736), "Solutio problematis ad geometriam situs pertinente" (PDF) , Commentarii Academiae Scientiarum Imperialis Petropolitanae , 8 : 128–140. Reimpreso y traducido en Biggs, NL; Lloyd, EK; Wilson, RJ (1976), Graph Theory 1736-1936 , Oxford University Press.
- Sabidussi, Gert (1964), "Infinite Euler graphs", Canadian Journal of Mathematics , 16 : 821–838, doi : 10.4153 / CJM-1964-078-x , MR 0169236.
- Veblen, Oswald (1912), "An Application of Modular Equations in Analysis Situs", Annals of Mathematics , Second Series, 14 (1): 86–94, doi : 10.2307 / 1967604 , JSTOR 1967604