Demostrar que hay un número par de caras cuyos vértices que todas las tres etiquetas en un gráfico que es triangular

Question

Considere la posibilidad de un plano de dibujo de un gráfico en todas sus caras, incluyendo la exterior, son triangulares (es decir, tiene 3 vértices). Para cada vértice, podemos asignar arbitrariamente una de las etiquetas 1,2,3. Probar que existe un número par de caras cuyos vértices conseguir los tres etiquetas.

Estoy tratando de demostrar lo anterior, y tengo muy cerca de mi intuición, pero todavía no estoy allí. Esto es lo que hice:

He asignado impar grado con tener todos los tres vértices. El rojo es el único que tiene todos ellos y el exterior, supongo. Sabemos que no puede ser sólo el rojo, porque por un apretón de manos lema sabemos que el número de vértices con grado impar es aún pero esta es una buena prueba? Y puedo asignar las cosas como yo lo hice?

Answer 1

Usted está en el camino correcto.

En primer lugar, en su ejemplo, la cara exterior no es triangular. En segundo lugar, usted no puede simplemente asignar impar grados, lo que debe hacer, es definir un gráfico de tal manera que el derecho de los vértices se han impar grados.

Así que vamos a definir un (multi)grafo $G'$ que tendrá los rostros de $G$ como vértices, y existe una arista entre dos vértices $f_1$ $f_2$ $G'$ (es decir, las caras de $G$) cuando:

1. Se enfrenta a $f_1$ $f_2$ comparten un borde en $G$.
2. Las etiquetas en los extremos de la arista compartida en $G$ son diferentes.

Técnicamente deberíamos hacer a $G'$ un multigraph, porque dos caras pueden compartir más de un borde. Con tal definición, de hecho, los vértices de $G'$ (que son caras de $G$) tienen un grado impar si y sólo si todos los tres etiquetas diferentes (grado cero si sólo hay un único etiquetas y grado dos, si hay dos etiquetas exclusivas).

Finalmente, si usted se siente incómodo con caras de $G$ como vértices de $G'$, puede asignar a los números, es decir, si $G$ $F \in \mathbb{N}$ caras, a continuación, vamos a número de ellos de forma arbitraria como la $f_1, f_2, \ldots, f_{F}$ y, a continuación, construir la gráfica de $G'$ en el conjunto de $\{1, 2, \ldots, F\}$. De esta manera hay una correspondencia uno a uno entre los vértices de $G'$ y las caras de $G$, por lo que todo el razonamiento funciona igual de bien. Ver también la definición de un grafo dual (por ejemplo, $G'$ es un subgrafo de el doble de $G$).

Espero que esto ayude a $\ddot\smile$