La comprensión de un hecho en una prueba de Brooks del teorema de

Question

En la página 90 de Harris, Hirst y Mossinghoff la Combinatoria y Teoría de grafos, Brooks del teorema se expresa de la siguiente manera:

Si $G$ es un grafo conexo que no es ni un extraño ciclo ni un grafo completo, a continuación, $\chi(G)\le\Delta(G).$

donde $\chi(G)$ es la cromática número de $G$$\Delta(G)=\max\{\deg v\mid v\in V(G)\}$.

Hay un hecho establecido en un subcase de la prueba de este teorema (Subcase 3b página 91) que yo no entendía. Bajo los supuestos de que:

• $k=\Delta(G)\ge3$;

• $G$ $k$- regular ;

• la conectividad de $G$$\kappa(G)=2$;

desde $G$ no está conectado, no existe vértices $u,w$ de manera tal que la gráfica de $G-\{v,w\}$ está desconectado. Deje que sus componentes se $G_1,\dots,G_t$. Desde $k\ge 3$, cada una de las $G_i$ tiene al menos $2$ vértices. Desde $w$ no es un corte de vértice (debido a $G$$2$ -), $v$ es adyacente a al menos un vértice en cada una de las $G_i$ (y lo mismo puede decirse de $w$).

Deje $u\in V(G_1)$ ser un vecino de $v$ y asumen $u$ es un corte vértice de $G-v$. Debe haber otro vértice $y$ $G_1$ tal que

(i) $y$ no es un recorte vértice de la gráfica de $G-v$, y

(ii) las únicas vías de $y$ $w$ $G-v$ir a través de vértice $u$.

Hechos (i) y (ii) es claro para mí. Uno puede ver esto considerando los componentes conectados de $G-\{u,v\}$. Aquí está el hecho de que no entiendo por qué se tiene:

Desde $u$ no es un vértice de corte de $G$ sí, debe ser eso $y$ es adyacente a $v$.

Para mí está claro que debe haber caminos en $G$ $y$ $w$que ir a través de vértice $v$, de lo contrario $u$ sería un corte vértice de $G$. Esto significa que $v$ tiene otro vecino en $G_1$. Pero no puedo ver por qué $y$ sí, es un vecino de $v$, o por qué hay un vecino de $v$ que satisface (i) y (ii). De nuevo teniendo en cuenta los componentes conectados de $G-\{u,v\}$, puedo ver por qué podemos encontrar vecinos de $v$ satisfactorio (ii), pero no veo por qué el hecho de como se señaló anteriormente sostiene. Me podrían ayudar por favor?

Answer 1

Esta respuesta se concibe como un complemento a Misha Lavrov respuesta. Esto demuestra que siempre podemos escoger un $y$ con el deseado tres propiedades.

En primer lugar, desde la $u$ es un corte vértice de $G - v$, hay un componente $G_1'$ $G-\{u,v\}$ tal que $V(G_1') \subseteq V(G_1)$$\Gamma(w) \cap V(G_1') = \emptyset$. Es claro que en cada vértice $G_1'$ va a satisfacer la condición (ii). Así queremos encontrar $y \in V(G_1') \cap \Gamma(v)$ satisfacer la condición (i).

Desde $u$ no es un vértice de corte de $G$, debemos tener la $\Gamma(v) \cap V(G_1') \neq \emptyset$. Decir $y_1 \in \Gamma(v) \cap V(G_1')$. Si $y_1$ no es un vértice de corte de $G - v$, tome $y = y_1$.

De lo contrario, nos dividimos $G_1'$ en partes de la siguiente manera. Deje $H_1$ ser el más grande subgrafo de $G_1'-y_1$ tal que $G[V(H_1) \cup \{u\}]$ está conectado (donde G[V] es el subgrafo inducido de $G$ con conjunto de vértices $V$). Deje $H_2' = G_1' \setminus (H_1 \cup \{y_1\})$. Desde $y_1$ no es un cutvertex de $G$,$y_2 \in H_2' \cap \Gamma(v)$.

Podemos repetir esta idea de encontrar una secuencia de elementos $y_i$. I definir conjuntos de vértices $H_{k+1}', H_k$ y elementos $y_{k+1} \in \Gamma(v) \cap H_{k+1}'$ tal que $H_k' = H_k \cup \{y_k\} \cup H_{k+1}'$ inductiva. Supongamos que hemos encontrado $y_{k} \in \Gamma(v) \cap H_{k}'$ y se definen los conjuntos de $H_k, H_{k+1}'$. Si $y_{k}$ no es un vértice de corte de $G - v$, tomamos $y = y_{k}$ y hemos terminado.

De lo contrario, ya que $y_{k}$ no es un cutvertex de $G$,$y_{k+1} \in \Gamma(v) \cap H_{k+1}'$. Deje $H_{k+1}$ ser el más grande subgrafo de $H_{k+1}' - y_{k+1}$ tal que $G[V(H_{k+1}) \cup \{y_k\}]$ está conectado y deje $H_{k+2}' = H_{k+1}' \setminus (H_{k+1} \cup \{y_{k+1}\})$.

Puesto que el $y_i$ son distintos vértices de $G_1'$, este proceso debe terminar en finitely pasos, por ejemplo, con el vértice $y_n$. Dado que el proceso ha terminado, $y_n$ no es un vértice de corte de $G - v$, por lo que podemos tomar $y = y_n$.

Edit: Este argumento fue difícil de escribir ya que realmente yo pensaba que era por el dibujo "la imagen de la derecha". A continuación, es un boceto de la subgrafo de $G_1'$ y el asociado subdivisiones generado por los tres primeros pasos del procedimiento iterativo.

Answer 2

Tienes razón en que $y$ no necesita ser adyacente a $v$.

Considere el siguiente gráfico:

Este gráfico es $3$-regular, $2$-conectado, y $\{v,w\}$ es uno de los posibles vértices de corte. Así es $\{u,v\}$ (equivalentemente, $u$ es un corte vértice de $G-v$).

El vértice $y$ en el diagrama satisface (i) y (ii): no es un corte vértice de $G-v$, y que todos los caminos de $y$ $w$ $G-v$ir a través de $u$. Sin embargo, no es adyacente a $v$.

---

Pero también, en el punto en la prueba donde tenemos un vértice de corte $\{u,v\}$ de dos vértices adyacentes, podemos simplemente el color de la gráfica inductivo: supongamos $H_1, H_2, \dots$ ser los componentes conectados de $G - \{u,v\}$, el color de cada una de las $H_i \cup \{u,v\}$ por un simple caso de Brooks del teorema, y luego combinar los colores a lo largo de $\{u,v\}$. Desde $u$ $v$ son adyacentes en todos estos subdiagramas, que nunca se puede dar el mismo color, por lo que es posible permutar los colorantes a estar de acuerdo en $u$$v$.