$G=(V,E_1 \cup E_2)$ es un gráfico libre de triángulos, donde $G_1=(V,E_1)$ es plana y $G_2 = (V, E_2)$ es un árbol. Pruébalo: $\chi (G) < 7$

Question

¿alguien puede ayudar con esto, cualquier dirección podría ser útil? He intentado usar el hecho de que $G_1$ satisface que es planar y es libre de triángulos porque G lo es. Así que deberíamos tener $|E_1| \leq 2|V|-4$ y para el árbol tenemos $|E_2| = |V|-1$ .

Así que en G tenemos $|E| \leq 3|V|-5$ de esto sabemos que $2|E| \leq 6|V|-10$ $\Rightarrow \exists v \in V : d(v)<6$ Ahora estoy pensando en la inducción pero realmente estoy atascado

Answer 1

Ya que quiere un argumento no inductivo, le proporcionaré uno. La afirmación que hay que demostrar es la siguiente:

Dejemos que $G(V,E)$ sea un gráfico sin triángulos en el conjunto de vértices $V$ con el conjunto de bordes $E$ . Supongamos que $E$ puede dividirse en dos conjuntos $E_1$ y $E_2$ tal que el subgrafo inducido por aristas $G\left[E_1\right]$ es plana, mientras que $G\left[E_2\right]$ es un bosque. Entonces, $\chi(G)<7$ .

Lo demostraremos por contradicción. Supongamos que existe un gráfico $G$ con $\chi(G)\geq 7$ . Claramente, $G$ tiene al menos $1$ vértice. Elija uno con el menor número de vértices. Por lo tanto, utilizando el mismo argumento sugerido por el OP (ahora con $\left|E_2\right| \leq |V|-1$ en lugar de la igualdad), existe un vértice $v$ de $G$ con $\deg_G(v)\leq 5$ . Definir $G'$ para ser el subgrafo inducido por vértices $G\big[V\setminus\{v\}\big]$ de $G$ . Desde $G'$ tiene un número menor de vértices y $G'$ también satisface la misma condición, debemos tener $\chi\left(G'\right)<7$ . Elige una coloración de vértices de $G'$ por un máximo de $6$ colores. Desde $v$ es adyacente a un máximo de $5$ vértices de $G'$ existe un color no mostrado entre los vecinos de $v$ . Extiende esta coloración de vértices en $G'$ a una coloración de vértices en $G$ por el colorido $v$ con uno de los colores no utilizados entre los vecinos de $v$ . Por lo tanto, $G$ tiene una coloración de vértices como máximo $6$ colores, contradiciendo la suposición de que $\chi(G)\geq 7$ . Es decir, dicho gráfico $G$ no puede existir.

P.D: Para ser justos, esto es una inducción disfrazada.