Una partición de los vértices de una gráfica

Question

Tengo un ejemplo para esta pregunta, pero hay muchos diferentes posibilidades y no sé cómo mostrar este para todos los gráficos. Tiene alguien algún consejo de cómo empezar ?

Deje $G=(V,E)$ ser un undirect gráfico.Prueba: No es una partición de a $V = V_1 \cup V_2$ de un verticesset, por lo que todos los vértices en $G[V_1]$ $G[V_2]$ tienen incluso un grado.'

Puedo dibujar en el papel,pero ¿cómo lo mencionó, no se ha probado de todo y no sé cómo. Gracias por cualquier consejo.

Answer 1

Nos acercamos a este problema a través de la inducción sobre el número de vértices, $|V|$. Trivialmente, la afirmación es verdadera cuando $|V|\leq 3$.

Asumir por parte de nuestros inducción de la hipótesis de que todos los gráficos en estrictamente menos de $n$ vértices satisface la pretensión de que existe alguna partición en dos conjuntos de vértices donde el subgrafo inducido en cada uno es tal que cada vértice es incluso de grado. Considere lo que ocurre, por arbitraria $G$ al $|V(G)|=n$.

Podemos suponer que la $G$ contiene al menos un vértice de grado impar (si no, aprovecha $V_1 = V$$V_2 = \emptyset$, trivialmente la satisfacción de la demanda). Elegir uno de esos vértices de grado impar y la etiqueta es $v$. Tome nota de el barrio de $v$ y la etiqueta es $\mathscr{N}(v)$.

La construcción de un nuevo gráfico de la original, definido como: $G' = (V(G)\backslash\{v\}, \{(x,y):~x\neq y, (x,y)\in E(G\backslash \mathscr{N}(v))\cup (E(\mathscr{N}(v)))^c\})$

Es decir, a la forma $G'$, invertir las relaciones de adyacencia entre los miembros de $\mathscr{N}(v)$, elimine $v$, y conservar el resto de la gráfica de la forma en que fue en $G$.

Ahora, $G'$ tiene menos vértices de $G$ y por nuestra hipótesis de inducción tiene alguna partición $V_1', V_2'$ de manera tal que todos los vértices en la inducida por subdiagramas de $G'$ son incluso de grado.

Definir $A = V_1'\cap \mathscr{N}(v)$ y definen $B = V_2'\cap \mathscr{N}(v)$

Como $v$ fue seleccionado para ser de grado impar, precisamente en una de $|A|$ o $|B|$ va a ser de tamaño uniforme. Sin pérdida de generalidad, supongamos que se $A$.

Volviendo ahora a la gráfica original, considere la posibilidad de la partición $V_1 = V_1'\cup\{v\}$ $V_2 = V_2'~~~~~$ (nota, si hubiera sido a$B$, lo que era de tamaño uniforme, adjuntar $\{v\}$ $V_2$lugar)

Tenga en cuenta que para cualquier vértice $x\in V_i\backslash\mathscr{N}(v)$, en las adyacencias son los mismos que en el subgrafo inducido de$G'$$V_i'$, y es por lo tanto, incluso de grado.

Para cualquier vértice en $A$, tendrá el mismo número de adyacencias a elementos fuera de $A$ como en el subgrafo inducido de $G'$ $V_1'$ (pares o impares$\star$), y se han $|A\backslash\{x\}|$ menos el número de adyacencias a otros elementos de $A$, mientras que en $G'$ (impar si $\star$ era extraño, incluso lo contrario), más 1 para la adyacencia a $v$. I. e., $d_{G(V_1)}(x) = d_{G'(V_1')}(x) + |A|-1-d_{G'(A')}(x)+1$ (que es aún + incluso - 1 - aun + 1 o es impar + incluso - 1 - impar + 1) y por lo tanto, incluso de grado.

Para cualquier vértice $x\in B$ $|B|$ fue asumido para ser impar, asimismo, ser $d_{G(V_2)}(x) = d_{G'(V_2')}(x) + |B|-1 -d_{G'(B')}(x)$ (que es aún + impar - 1 - par o es impar + impar - 1 - impar) y también incluso de grado.

Para $v$ sí, sólo adyacencias son a $A$, el cual fue asumido a ser de tamaño uniforme, y por lo $d(v)=|A|$ es incluso.

Por lo tanto, todos los vértices son incluso de grado, en sus respectivos inducida por subdiagramas y la demanda se demuestra.