Constructiva de la prueba, se utiliza la siguiente Lema:
Lema: Si $G(V,E)$ es un grafo conectado, gráfico, el conjunto de vértices $V$ se puede dividir en dos conjuntos de $V_1$ $V_2$ de manera tal que en
los dos subdiagramas inducida por $V_1$$V_2$, el grado de cada uno de los
vértice es par.
Para utilizar este lema a su problema, supongamos $H$ corresponde a la gráfica dada y supongamos $H$ tiene al menos un vértice incluso de grado. Se añade un nuevo vértice $O$ y hacer que sea adyacente a cada uno de sus vértices. Si no hay ningún vértice incluso de grado, no hacemos nada. Cada vértice (excepto posiblemente $O$) es de grado impar en el nuevo gráfico.
Esta nueva gráfica tiene una partición de $V_1,V_2$, según el Lema anterior. Elegir la partición que no contenga $O$ (es decir $V_1$) como voltear su conjunto. Desde cualquier vértice en $V_1$ es incidente a un número par de vértices en $V_1$, mueven de un tirón, y desde cualquier vértice en $V_2$ (excepto posiblemente $O$) es incidente a un número impar de vértices en $V_2$, mueven de un tirón.
El lema ha inductivo prueba (que se puede convertir en un algoritmo).
La prueba del Lema:
Procedemos por inducción sobre $|V|$. Bases de los casos son fáciles de comprobar.
Supongamos $G(V,E)$ es un grafo grafo conexo con $|V| = n+1$.
Si todos los vértices de $G$ son incluso de grado, se realiza mediante la toma de $V_1 = V$ $V_2 = \emptyset$
Supongamos $v$ es un vértice con grado impar, cuyos vecinos se $v_1, v_2, \dots, v_k$.
Formar un nuevo gráfico de $G'$ como sigue:
Si $v_i$ $v_j$ son adyacentes en $G$, eliminar el borde de unirse a ellos. Si $v_i$ $v_j$ no son adyacentes en $G$, agregar un nuevo borde de unirse a ellos.
Borrar $v$.
Aplicar la hipótesis de inducción a $G'$, dicen que llegar a ser $V'_1$$V'_2$. Uno de $V'_1$, $V'_2$ debe contener un número de $v_i$, decir $V'_1$.
Es fácil comprobar que la partición de $G$ que estamos buscando es $V_1 = V'_1 \cup \{v\}$$V_2 = V'_2$.
$\square$
El de arriba inductivo prueba puede ser utilizado para dar un $\mathcal{O}(|V|^3)$ algoritmo de tiempo, creo. (Por supuesto, el álgebra lineal manera de resolver este específico luces podría dar la misma). Tal vez un mejor/inteligente de representación/camino puede hacer sub-cúbicos.
También hay un elegante álgebra Lineal (existencial) de la prueba debido a Noga Alon, lo que demuestra que el vector diagonal (haciendo un vector de fuera de la diagonal principal) de una $nxn$ matriz $A$ $\mathbb{F}_2$ es en su fila espacio.
Tanto las pruebas (por encima de la valoración crítica y el Álgebra Lineal Prueba por Noga Alon) se puede encontrar en el libro: "los Problemas de Combinatoria y Ejercicios" por Laci Lovasz.
