Teorema de Veblen

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 grado par . Por lo tanto, está estrechamente relacionado con el teorema de Euler (1736) que establece que un grafo finito tiene un recorrido euleriano (un único ciclo no simple que cubre las aristas del grafo) si y solo si es conexo y cada vértice tiene grado par. De hecho, una representación de un grafo como una unión de ciclos simples puede obtenerse a partir de un recorrido euleriano dividiendo repetidamente el recorrido en ciclos más pequeños cuando hay un vértice repetido. Sin embargo, el teorema de Veblen también se aplica a grafos disconexos y puede generalizarse a grafos infinitos en los que cada vértice tiene grado finito. ^{[ 1 ]} 

Si un grafo G infinitamente numerable no tiene vértices de grado impar, entonces puede escribirse como una unión de ciclos simples (finitos) disjuntos si y solo si todo subgrafo finito de G puede extenderse (incluyendo más aristas y vértices de G ) a un grafo euleriano finito. En particular, todo grafo infinitamente numerable con un solo extremo y sin vértices impares puede escribirse como una unión de ciclos disjuntos. ^{[ 1 ]}

• Base cíclica
• Conjetura de doble cubierta de ciclo
• matroide euleriano

• Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis" (PDF) , Commentarii Academiae Scientiarum Imperialis Petropolitanae , 8 : 128-140Reimpreso y traducido en Biggs, NL ; Lloyd, EK; Wilson, RJ (1976), Graph Theory 1736–1936 , Oxford University Press.
• Sabidussi, Gert (1964), "Grafos de Euler infinitos", Canadian Journal of Mathematics , 16 : 821–838 , doi : 10.4153/CJM-1964-078-x , MR 0169236 .
• Veblen, Oswald (1912), "Una aplicación de ecuaciones modulares en análisis situs", Annals of Mathematics , Segunda serie, 14 (1): 86– 94, doi : 10.2307/1967604 , JSTOR 1967604