# If $G$ is biconnected and $\delta(G) \geq 3 \Rightarrow \exists v: G-v$ is also biconnected.

If $G$ is biconnected and $\delta(G) \geq 3 \Rightarrow \exists v: G-v$ is also biconnected.

Where $\delta (G) -$ minimum degree of all vertices, $G-v$ is equal to if we remove this vertex from $G$

Thanks!

-
Where did you found this problem? –  Jernej Sep 29 '12 at 10:33
@Azoo This is problem from the teacher's book from the University. Is something wrong with this problem? –  jofisher Sep 29 '12 at 13:18
No its just that I never heard of any similar problem. –  Jernej Sep 29 '12 at 14:53
do you happen to have an example of a 2-connected graph with minimal degree 3 such that there is a vertex whose removal makes the graph 1-connected? –  Jernej Sep 29 '12 at 16:45
@Azoo This is example: i.imgur.com/Zfcfg.png. Please remove the central vertex. –  jofisher Sep 30 '12 at 14:20
show 1 more comment

Unfortunately, the most I can do is provide a reference for the result.

A much stronger statement than the one in question is proven here in the paper Critically $n$-connected graphs by Gary Chartrand, Agnis Kaugars and Don R. Lick.

Specifically they define a critically $n$-connected graph to be an $n$-connected graph for which the removal of any vertex will reduce the connectivity by $1$. They prove that any such graphs must have a vertex of degree less than $\frac{3n-1}{2}$ (and that this bound cannot be improved).

They do provide a reference to a paper [A theorem on on the removal of vertices from blocks by A. Kaugars] which explicitly proves the case for $n=2$ which is what we're interested in. Unfortunately, it does not seem easy to get access to said paper (unless somebody here happens to attend the Kalamazoo College).

-
Thanks for digging up this reference. It seems (from a very cursory glance) that the Chartrand/Kaugars/Lick paper has a self-contained proof of this result for general $n \ge 2$, so you don't need the second paper to understand it. –  Lukas Geyer Oct 18 '12 at 20:02
@LukasGeyer Yes. But I suspect that the proof for $n=2$ would be much simpler than the general case, which might suit the OP's needs a bit more. Plus, it never hurts to have another proof. –  EuYu Oct 18 '12 at 21:31
Thank you for the link. Gorgeous skill. Thanks for your help! –  jofisher Oct 19 '12 at 6:55

It's not a full answer, but it might be a useful direction (I've haven't followed it all the way through).

Consider a maximal path $x_0 x_1 \ldots x_n$ in $G$. Because it's maximal, all the neighbors of $x_0, x_n$ mus be in the path itself (see also http://math.stackexchange.com/a/212052/44541), and due to the bi-connectivity, it's actually a cycle (as $x_0$ and $x_n$ must be connected directly.

If we examine every other vertex in the graph, all it's neighbors are in the graph as well (or we could construct a longer path due to the bi-connectivity with the neighbor not in the cycle. This creates a maximal cycle where each vertex is also part of a chord edge.

Intuitively, this should ensure that there are enough way to "bypass" one of the vertices, such as to fulfill the statement. But I haven't pursued it further yet.

-
Thank you for your made work! This is useful in some way. –  jofisher Oct 14 '12 at 19:40
“all its neighbors are in the graph as well” : you mean in the path as well, right ? –  Ewan Delanoy Oct 16 '12 at 16:33
The statement "and due to the bi-connectivity, it's actually a cycle" is false. Consider a cycle graph with a single vertex of degree two embedded at the center. Clearly if we start at the center vertex and traverse the cycle we will have a path of maximal length. But the end points are not directly connected. –  EuYu Oct 17 '12 at 14:01