Exposicion

Andres Lopez MartnezFacultad de Ciencias, Universidad Nacional Autonoma de Mexico

Noviembre 15, 2014

Teorema: Toda grafica 2k -regular contiene un 2 -factor.

Prueba: Sea G cualquier grafica 2k -regular con V (G) = {v1, ..., v2}. Podemos asumir, sinperdida de generalidad, que G es conexa. (En caso contrario, podemos smplemente consid-erar a las componentes de G por separado.) Dado que todo vertice tiene grado par, se sabeque G tiene un tour Euleriano T. (El cual es el camino que recorre todas las aristas de unagrafica tocando cada arista una sola vez; regresando al punto de partida). Este camino usatodas las aristas, pero puede visitar vertices mas de una vez. Ahora bien, usamos a T paraconstruir un nuevo grafico bipartito H con biparticion (U,W ), donde U = {u1, u2, ..., un} yW = {w1, w2, ..., wn}. De aqu vemos que hay una arista entre ui y wj si y solo si vj se sigueinmediatamente de vi en T. Dado que para cada vertice en G hay k aristas que entran y karistas que salen a lo largo de T, vemos que H es k -regular y, por lo tanto, 1 -factorizable (comose mostro en clase). Sean M1, ...,Mk los k 1-factores, podemos identificar a las aristas de Micon la etiqueta i, 1 i k. Entonces, las k aristas incidentes a cada ui de H reciben las ketiquetas 1, 2, ..., k y, por lo tanto, si las aristas uiwj y ujwr estan en Mp, 1 p k, identi-ficando el vertice wj con el vertice uj para cada j en Mp, se obtiene un etiquetado de aristasa G en donde las aristas vivj y vjvr reciben la etiqueta p. De aqu, es claro que las aristas deMp inducen un 2-factor de G con etiqueta p. Ahora bien, notemos que ui no es adyacente awi en H, 1 i k. Dado que esto es cierto para cada uno de los 1-factores Mp, 1 p k,obtenemos as una 2-factorizacion de G en k 2-factores

Ejemplo: Grafica 4-regular.

G : T :

Figure 1: Grafo 4-regular de orden 8, junto con un tour Euleriano T que lo recorre.

1

H :

Figure 2: Grafica bipartita H construida a partir de T con biparticion (U,W ).

M1 : M2 :

Figure 3: 1-factores M1 y M2 obtenidos de la grafica bipartita 2-regular H.

2

Figure 4: Etiquetado de aristas en G a partir de los 1-factores M1 y M2 de H.

Figure 5: 2-factores de G inducidos de los 1-factores de H; donde, su union es una 2-factorizacionde G.

3