Agregar un vértice en G, de manera que el nuevo grafo es Euleriano

Question

La pregunta dice, "Vamos a $G = (V, E)$ ser un grafo conexo que no es Euleriano. Demostrar que es posible añadir un vértice a $G$, junto con algunos de los bordes de los nuevos vértices a algunos de los antiguos vértices de $G$, de modo que el nuevo grafo es Euleriano."

Hasta el momento lo que tengo para que mi respuesta es la siguiente, y quiero ver si me estoy dirigiendo en la dirección correcta:

"Vamos a $u, v \in V$. $u$ está conectado a $v $. Esto significa que hay un $(u, v)$-camino de $G$. Supongamos $d(u)$ $d(v)$ son impares. Vamos a añadir un vértice a $V$; es decir, $w$. También vamos a añadir algunas aristas incidentes a $w$ y los vértices de grado impar. Ahora, $d(u)$ $d(v)$ son incluso. $d(w) = 2$, lo $d (w)$ es incluso así. $\forall v \in V, d(v)$ es incluso. No hay vértices de grado impar, por lo $G$ ahora es Euleriano."

Cualquier ayuda se agradece!

Answer 1

De forma más concisa, se agrega un nuevo vértice $w$, y de la conexión a todos los vértices de la gráfica original que había impar grado. Esto hace que todos los vértices tienen aún grado, pero es necesario comprobar el grado de $w$.

El grado de $w$ es el número de pares de grado de los vértices en la gráfica original, que es también, incluso (considerar el total de grados de la gráfica original). En particular, el grado de $w$ no es necesariamente $2$; no estoy seguro de por qué sólo se consideran dos pares de vértices de grado.

Finalmente, como otros han señalado, el grado de $w$ no es cero otra cosa de la gráfica original ya habría sido Euleriano.

Answer 2

El uso de apretón de manos lema, el número de vértices con grado impar en un gráfico es aún. Así, añadir un borde a partir de este nuevo vértice a todos los vértices con grado impar en el anterior gráfico, haciendo que el grado de todos los vértices incluso.
Y ahora con la caracterización de Euler Gráficos, el nuevo grafo es Euleriano.
Como @darji ha dicho con razón, el nuevo gráfico está conectado porque el nuevo añadido de vértices está conectado por lo menos un vértice, y como el gráfico original estaba conectado(no tiene ningún aislado de vértice), el nuevo gráfico también está conectado.