4
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

Consider the graph below:

enter image description here

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$.

$\endgroup$
  • $\begingroup$ Thank you very much for your help! So your answer shows that $y$ may satisfy (i) and (ii) but not (iii), unlike what's said in the book. However I still can't see why there exists $y$ that satisfies (i), (ii) and (iii). The aim in the proof is to prove that $v$ has a neighbor in $G_1$ that is not a cut vertex of $G-v$. In your graph that's indeed vertex $x$, but I couldn't find a proof. $\endgroup$ – Scientifica Aug 26 '18 at 15:25
  • $\begingroup$ You're right - I read your answer and assumed that you could always find such a vertex, but I see now that you only have a way to find a vertex satisfying (ii) and (iii) but not (i). I don't see offhand how to do it, but in the meantime I've included a simpler way to finish the proof. $\endgroup$ – Misha Lavrov Aug 26 '18 at 15:28
  • $\begingroup$ I see. That indeed finishes the proof. Thank you very much! $\endgroup$ – Scientifica Aug 26 '18 at 21:41
2
$\begingroup$

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.

enter image description here

$\endgroup$
  • $\begingroup$ Thank you for your help! Your answer sated my curiosity about the existence of such a point! $\endgroup$ – Scientifica Aug 26 '18 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.