Probar que cada plano gráfico sin un triángulo (es decir, un ciclo de longitud tres) tiene un vértice de grado tres o menos. Entonces, probar que todos los grafos planares sin triángulos son cuatro engañosa sin el uso de la cuatro-color teorema.
Este es un problema en mi libro de texto que no tiene solución. Cómo abordar esto? La inducción parece no funcionar.
Para la primera parte podemos utilizar de Euler $F-E+V=2$ donde $F$ es el número de caras (contando la cara que incluye $\infty$), $E$ es el número de aristas, y $V$ el número de vértices.
Si no hay triángulos, a continuación, cada cara está rodeada por al menos $4$ bordes. Por lo $4F/2<E$, es decir,$F<E/2$. De esto podemos obtener $V>E/2+2$. Si todos los vértices tienen el fin de $\geq4$$4V/2<E$, es decir,$V<E/2$. De esto podemos obtener $0>2$. Así, no podemos tener ninguna triángulos y, al mismo tiempo, todos los vértices con grado de $\geq4$.
Para la segunda parte toma un vértice que tiene el grado $\leq3$. El Color y sus vecinos con diferentes colores $A,B,C,D$. Podemos hacer esto sólo porque tiene el grado $\leq3$. Podemos eliminar este vértice y los bordes insident. Si tenemos en color que el resto de la gráfica siempre hay una manera de que el color del vértice eliminado. Observa que la gráfica con este vértice eliminado todavía no tiene triángulos, pero menos vértices. Aplicar inducción sobre el número de vértices ahora.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
