Probar un gráfico que contiene vértices impares de $2k$ contiene $k$ distintos senderos

Question

Estoy leyendo el libro de los Gráficos y Sus Usos , que contiene el siguiente teorema y de la prueba:

TEOREMA 2.3. Un grafo conexo con 2k impar de vértices contiene una familia de k distintos senderos que, juntos, recorrer todas las aristas de la gráfica exactamente una vez.

PRUEBA. Deje que el impar de vértices en la gráfica se denota por en un cierto orden.

$a_1,a_2,\dots,a_k$ $b_1,b_2,\dots,b_k$

Cuando añadimos la $k$ bordes $a_lb_l, a_2b_2 ,\dots, a_kb_k$ a el gráfico, todos los los vértices se vuelven aún y hay un camino Euleriano T. Cuando estos los bordes se dejó caer de nuevo, T cae en k caminos por separado cubriendo los bordes de la gráfica original.

Sin embargo, esto no parece tener sentido ya que en el grafo cuyos vértices tienen grado 3, 1, 1, 1 no hay manera de agregar 2 bordes de tal manera que el grado de todos impar de vértices se vuelve aún.

Lo que me estoy perdiendo aquí?

Answer 1

Veo mi problema, estoy pensando en términos de gráficos simples, pero este teorema está pensando en términos de multigraphs. Si agrega un borde entre 3 y 1 y entre 1 y 1 entonces todos los vértices se convierten incluso y hay un ciclo de Eulerian en el gráfico. Quitarle los bordes nuevos y obtendrá un gráfico en el que cada borde entre vértices de grado impar convierte el camino propio.