stringtranslate.com

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) de que un grafo finito tiene un recorrido de Euler (un solo 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 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 también se aplica a grafos desconectados y puede generalizarse a grafos infinitos en los que cada vértice tiene 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 (al incluir más aristas y vértices de G ) a un grafo euleriano finito. En particular, cada grafo infinito numerable con un solo extremo y sin vértices impares puede escribirse como una unión de ciclos disjuntos (Sabidussi 1964).

Véase también

Referencias