Coloración de bordes de gráficos bipartitos

Question

Un teorema de König dice que

Cualquier gráfico bipartito $G$ tiene un borde para colorear con $\Delta(G)$ (máximo grado) de colores.

Este documento demuestra que en la página 4:

1. Demostrar el teorema para regular bipartito gráficos;
2. Alegando que si $G$ bipartito, pero no $\Delta(G)$-regular, se puede agregar bordes a obtener un $\Delta(G)$-regular bipartito gráfico.

Sin embargo, parece ser que hay dos problemas con el segundo punto:

• Regular bipartito gráfica tiene el mismo número de vértices en las dos particiones. Así que tenemos que añadir vértices también.
• No estoy seguro de que siempre es posible agregar bordes a obtener un $\Delta$-regular bipartito gráfico, incluso si tenemos el mismo número de vértices. Vea la figura de abajo. B y E tienen un grado dos, pero no podemos hacerlos grado 3

Estoy en lo cierto ? Es allí una manera de corregir eso ?

Answer 1

Usted tiene que estar permitido añadir vértices. En ese caso se puede demostrar por inducción sobre el número de aristas:
Suponga que G' := G \ e es un Subgrafo de algunos Δ'-regular bipartito Gráfico de K'.
1. Caso Δ = Δ' + 1:
K = K' plus e más una ventaja para todos los otros dos vértices.
2. Caso e es en la K':
K = K'
3. Caso e no se en K':
Sea e = (a,b). Debido a que no aumente Δ, debe ser de los bordes en la K' \ G' f = (a,c) y g = (b,d). Hacer una copia de K' =: K" y unirse a ellos. Retire f, g y sus copias. Conectar e de la copia de correo, (a,c'), (b,d), (a',c), (b,d). Aquí un' es la copia de una etc.. Esto da K con todos los bordes derecho y grados.

Podemos iniciar la inducción a 0 los bordes, y tomar como K un edgeless bipartito Gráfico con las particiones del mismo tamaño, de manera que incluya G.

Caso 3 puede hacerse a veces sin la duplicación de la gráfica, pero no siempre. Su ejemplo es un caso, que puede ser resuelto por la duplicación de la gráfica. Añadiendo vértices, además, no es problema para el punto 1, porque es independiente de la cantidad de vértices.