Necesito ayuda para completar una prueba que escribí (o ver una solución más sencilla para el mismo problema).
Para obtener una lista de rutas $P_1, \ldots , P_m$ , dejemos que $L(P_1, \ldots, P_m)$ sea el número de caminos en $P_1, \ldots, P_m$ que no están cerradas. Sea $\tau(G)$ sea el menor valor de $L(P_1, \ldots, P_m)$ sobre todas las listas pf caminos $P_1,\ldots, P_m$ de manera que sus conjuntos de aristas se dividan $E(G)$ (es decir, cada arista de $G$ aparece exactamente en un camino). Por ejemplo, si $G$ es un ciclo con una arista más, entonces $\tau(G) = 1$ . Determine una expresión sencilla para $\tau(G)$ en términos de los grados de los vértices de $G$ .
Dejemos que $A = \{v \in V(G): \operatorname{deg}(v)$ es impar $\}$ . Primero demostramos que $\tau(G) \leq \frac{|A|}{2}$ .
Dejemos que $v \in A$ . Inicie un camino desde $v$ y seguir añadiendo aristas hasta que no sea posible añadir más aristas al camino. Cada vez que el camino pasa por un vértice $x$ reduce el grado de $x$ por $2$ . El camino no puede terminar en un vértice de grado par, por el hecho anterior. Por lo tanto, el camino termina en algún $v' \in A$ . Desde $v$ tiene un título impar, $v' \neq v$ .
Ahora, considere el gráfico $G^{(1)} - \{e \in E(G): e$ es una arista del camino anterior $\}$ . Sea $A^{(1)}$ sea el conjunto de todos los vértices de $G^{(1)}$ con el grado de impar. Se puede ver fácilmente que $A^{(1)}=A-\{v, v'\}$ . Continúe el procedimiento hasta $A^{(n)} = \varnothing$ . Entonces, los únicos vértices que quedan son los de grado par, y las aristas restantes pueden dividirse en caminos cerrados. Aquí, $L(P_1, \ldots, P_m) = \frac{|A|}{2}$ .
Ahora, queda por demostrar que no puede ser el caso que $\tau(G) < \frac{|A|}{2}$ .
