Proving that $G-\{x_1,x_2\}$ is connected if $G-v$ is $1$-connected and $x_1$ and $x_2$ belong to different blocks

159 Views Asked by At

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 :-)