Understanding a fact in a proof of Brooks's theorem

Question

In page 90 of Harris, Hirst and Mossinghoff's Combinatorics and Graph Theory, Brooks's theorem is stated as follows:

If $G$ is a connected graph that is neither an odd cycle nor a complete graph, then $\chi(G)\le\Delta(G).$

where $\chi(G)$ is the chromatic number of $G$ and $\Delta(G)=\max\{\deg v\mid v\in V(G)\}$.

There's a fact stated in a subcase of the proof of this theorem (Subcase 3b page 91) that I didn't understand. Under the assumptions that:

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

• $G$ is $k$-regular ;

• the connectivity of $G$ is $\kappa(G)=2$;

since $G$ is not connected, there exists vertices $u,w$ such that the graph $G-\{v,w\}$ is disconnected. Let its components be $G_1,\dots,G_t$. Since $k\ge 3$, each $G_i$ has at least $2$ vertices. Since $w$ isn't a cut vertex (because $G$ is $2$-connected), $v$ is adjacent to at least one vertex in each $G_i$ (and the same can be said for $w$).

Let $u\in V(G_1)$ be a neighbor of $v$ and assume $u$ is a cut vertex of $G-v$. There must be another vertex $y$ of $G_1$ such that

(i) $y$ is not a cut vertex of the graph $G-v$, and

(ii) the only paths from $y$ to $w$ in $G-v$ go through vertex $u$.

Facts (i) and (ii) are clear to me. One can see this by considering the connected components of $G-\{u,v\}$. Here's the fact that I don't understand why it holds:

Since $u$ is not a cut vertex of $G$ itself, it must be that $y$ is adjacent to $v$.

It is clear to me that there must be paths in $G$ from $y$ to $w$ that go through vertex $v$, otherwise $u$ would be a cut vertex of $G$. This means that $v$ has another neighbor in $G_1$. But I can't see why $y$ itself is a neighbor of $v$, or why there's a neighbor of $v$ that satisfies (i) and (ii). Again by considering the connected components of $G-\{u,v\}$, I can see why we can find neighbors of $v$ satisfying (ii), but I can't see why the fact as stated above holds. Could you help me please?

Answer 1

You are right that $y$ does not need to be adjacent to $v$.

Consider the graph below:

This graph is $3$-regular, $2$-connected, and $\{v,w\}$ is one possible vertex cut. So is $\{u,v\}$ (equivalently, $u$ is a cut vertex of $G-v$).

The vertex $y$ in the diagram satisfies (i) and (ii): it is not a cut vertex of $G-v$, and all paths from $y$ to $w$ in $G-v$ go through $u$. However, it is not adjacent to $v$.

---

But also, at the point in the proof where we have a vertex cut $\{u,v\}$ of two adjacent vertices, we can simply color the graph inductively: let $H_1, H_2, \dots$ be the connected components of $G - \{u,v\}$, color each $H_i \cup \{u,v\}$ by a simpler case of Brooks's theorem, and then combine the colorings along $\{u,v\}$. Since $u$ and $v$ are adjacent in all of these subgraphs, they will never be given the same color, so it's possible to permute the colorings to agree on $u$ and $v$.

Answer 2

This answer is intended as a supplement to Misha Lavrov's answer. It will show that we can always pick a $y$ with the desired three properties.

Firstly, since $u$ is a cut vertex of $G - v$, there is a component $G_1'$ of $G-\{u,v\}$ such that $V(G_1') \subseteq V(G_1)$ and $\Gamma(w) \cap V(G_1') = \emptyset$. It is clear that any vertex in $G_1'$ will satisfy condition (ii). So we want to find $y \in V(G_1') \cap \Gamma(v)$ satisfying condition (i).

Since $u$ is not a cut vertex of $G$, we must have that $\Gamma(v) \cap V(G_1') \neq \emptyset$. Say $y_1 \in \Gamma(v) \cap V(G_1')$. If $y_1$ is not a cut vertex of $G - v$, take $y = y_1$.

Otherwise, we split $G_1'$ into parts as follows. Let $H_1$ be the largest subgraph of $G_1'-y_1$ such that $G[V(H_1) \cup \{u\}]$ is connected (where G[V] is the induced subgraph of $G$ with vertex set $V$). Let $H_2' = G_1' \setminus (H_1 \cup \{y_1\})$. Since $y_1$ is not a cutvertex of $G$, there is $y_2 \in H_2' \cap \Gamma(v)$.

We can iterate this idea to find a sequence of elements $y_i$. I define vertex sets $H_{k+1}', H_k$ and elements $y_{k+1} \in \Gamma(v) \cap H_{k+1}'$ such that $H_k' = H_k \cup \{y_k\} \cup H_{k+1}'$ inductively. Suppose we have found $y_{k} \in \Gamma(v) \cap H_{k}'$ and defined the sets $H_k, H_{k+1}'$. If $y_{k}$ is not a cut vertex of $G - v$, we take $y = y_{k}$ and we are done.

Otherwise, since $y_{k}$ is not a cutvertex of $G$, there is $y_{k+1} \in \Gamma(v) \cap H_{k+1}'$. Let $H_{k+1}$ be the largest subgraph of $H_{k+1}' - y_{k+1}$ such that $G[V(H_{k+1}) \cup \{y_k\}]$ is connected and let $H_{k+2}' = H_{k+1}' \setminus (H_{k+1} \cup \{y_{k+1}\})$.

Since the $y_i$ are distinct vertices of $G_1'$, this process must terminate in finitely steps, say with the vertex $y_n$. Since the process terminated, $y_n$ is not a cut vertex of $G - v$ and so we may take $y = y_n$.

Edit: This argument was hard to write down since really I thought of it by drawing "the right picture". Below is a sketch of the subgraph of $G_1'$ and the associated subdivisions generated by the first three steps of the iterative procedure.