I was reading the proof of Brook's Theorem in Bollobas'$\,$ $\textit{Modern Graph Theory}$ $\,$ book (pages 148-149) and there is one claim that Bollobas makes, but does not prove.

Suppose that $G$ is $k$-regular with $k\geq 3$. Also suppose that $G$ is $2$-connected, but not $3$-connected. Then there exists a vertex $v$ such that $G-v$ is $1$-connected, and thus has at least two blocks, call them $B_1$ and $B_2$. Let $x_1$ and $x_2$ be vertices belonging to $B_1$ and $B_2$, respectively.

Here is the claim: $G-\{x_1,x_2\}$ is connected.

I have been trying to prove this claim in order to believe it! I believe that if you try assuming that $G-\{x_1,x_2\}$ is disconnected then you will end up contradicting that $G-v$ is $1$-connected. Somehow we could demonstrate that $v$ would be a cut vertex because there must not exist a path connecting $B_1$ and $B_2$, but there are details missing.

If anyone sees a nice proof for this, I would love to see it and I would be very appreciative! Thank you :-)

  • $\begingroup$ Wouldn't $C_4$ be a counterexample? It's $2$-connected but not $3$-connected. If you remove a vertex $v$, you get a path with three vertices. Pick $x_1,x_2$ to be the two vertices that are on the two ends of the path; clearly they belong to different blocks. However, $C_4-\{x_1, x_2\}$ is disconnected. $\endgroup$
    – benguin
    Nov 28 '16 at 0:17
  • $\begingroup$ @benguin I apologize! I forgot to mention two crucial details - $G$ is $k$-regular and $k\geq 3$. I will edit my post now. Thank you very much. $\endgroup$
    – Sarah
    Nov 28 '16 at 0:23
  • $\begingroup$ I have no experience with $k$-connectedness, but intuitively it seems to me that the following should work: Assume the contrary. Thus, the graph $G - \left\{x_1, x_2\right\}$ is the union of two nonempty vertex-disjoint subgraphs $G_1$ and $G_2$. Pick any two vertices $g_1$ and $g_2$ of $G_1$ and $G_2$, respectively. Since adding back either of $x_1$ and $x_2$ to the graph $G - \left\{x_1, x_2\right\}$ restores connectedness, we must have a path from $g_1$ to $g_2$ passing through $x_1$ but not through $x_2$, and we must have a path from $g_2$ to $g_1$ passing through $x_2$ but ... $\endgroup$ Nov 29 '16 at 19:45
  • $\begingroup$ ... not through $x_1$. Combining these paths, we can find a cycle passing through both $x_1$ and $x_2$. Now, I hope that this cycle is a simple cycle, and does not pass through $v$. Therefore, it gives two paths between $x_1$ and $x_2$ in the graph $G - \left\{v\right\}$ that have no internal vertex in common. This contradicts the fact that $x_1$ and $x_2$ lie in different blocks of this graph. So... it remains to prove that my hope is correct. $\endgroup$ Nov 29 '16 at 19:47
  • $\begingroup$ OK, the first half of the hope is true, if we choose the paths correctly: Namely, we choose the path from $g_1$ to $g_2$ in such a way that it first stays inside $G_1$, then moves to $x_1$, then goes into $G_2$ and stays there. Similarly for the other path. The cycle obtained by combining these two paths might not be simple, but we can make it simple by removing subcycles that are completely contained in one of $G_1$ and $G_2$, and the result will be a simple cycle passing through $g_1$ and $g_2$. Remains to ensure that it does not contain $v$. $\endgroup$ Nov 29 '16 at 19:49

Since the graph is 2-connected, if $G-\{x_1,x_2\}$ is disconnected, $G-\{x_1\}$ and $G-\{x_2\}$ must both be connected. Since $B_1$ and $B_2$ are distinct endblocks, $G-\{x_1\}$ being connected meant that $v$ is connected to some other vertices in $B_1$ to make it connected. The same goes for $B_2$. Since $x_1$ and $x_2$ belong to different blocks, there is no edge between them and this meant that $G-\{x_1,x_2\}$ must be connected.


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.