Prueba que implica el subgrafo de un árbol

Question

Dejemos que $T$ sea un árbol con un número par de vértices. Demostrar que $T$ tiene "exactamente" un subgrafo de extensión en el que todos los vértices tienen grado impar.

Sólo podía pensar en este resultado: En un árbol con número par de vértices, el número de vértices con un número impar de hijos es impar.

Pero no sé cómo proceder. Estoy estudiando por mi cuenta la matemática discreta y encontré esta pregunta en un libro de matemática discreta.

EDITAR:

El post enlazado en los comentarios demuestra la existencia de dicho árbol. Esta pregunta también requiere la prueba de la unicidad.

Answer 1

Aquí hay una prueba rápida de la singularidad; el post enlazado ya cubre la existencia de múltiples maneras.

Dejemos que $G_1, G_2$ sean dos subgrafos Impares de $T$ . Entonces su diferencia simétrica $G_1 \mathbin{\Delta} G_2$ (que tiene cada arista encontrada en exactamente una de $G_1$ o $G_2$ ) es un subgrafo par de $T$ Todos los vértices tienen un grado par, posiblemente $0$ .

Supongamos que el subgrafo par tiene algún vértice de grado positivo. Entonces empieza en uno de esos vértices y da un paseo, sin repetir una arista, hasta que vuelvas a un vértice que hayas visto antes. (Nunca te quedarás atascado, porque ningún vértice de $G_1 \mathbin{\Delta} G_2$ tiene grado $1$ . Si introduce un vértice, puede dejarlo).

Pero ahora hemos encontrado un ciclo en $T$ ¡! Esto es imposible: los árboles no tienen ciclos. Así que $G_1 \mathbin{\Delta} G_2$ no puede tener ningún vértice de grado positivo - en otras palabras, es el gráfico vacío. Por lo tanto, $G_1 = G_2$ .