Dejemos que $G$ sea un gráfico. Quiero mostrar que $E(G)$ es la unión disjunta $C\cup D$ donde $C$ y $D$ pertenecen al ciclo y al espacio de corte respectivamente.
Respuesta
¿Demasiados anuncios?
Obsérvese que el resultado dice que podemos particionar $G$ en $V_1,V_2$ de tal manera que todos los vértices de $G[V_1]$ y $G[V_2]$ tienen un grado par. Una prueba de esto se da en Problemas y ejercicios combinatorios (Lovász):
Si todos los vértices tienen grado par entonces hemos terminado. Supongamos que $v$ es un vértice de grado impar con vecinos $N$ . Sea $G'$ sea el gráfico dado por la eliminación de $v$ y luego añadir una arista módulo $2$ entre todos los pares de elementos de $N$ .
Por la hipótesis de inducción podemos dividir $G'$ en $W_1,W_2$ .
Sin pérdida de generalidad, podemos suponer que $|N \cap W_1|$ es par y $|N \cap W_2|$ es impar, por lo que podemos establecer $V_1=W_1 \cup \{v\}$ y $V_2=W_2$ y comprueba que todo tiene un grado uniforme como se requiere.
