Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

Give some clue please!


share|cite|improve this question
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? – brainail 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: Please remove the central vertex. – brainail Sep 30 '12 at 14:20

2 Answers 2

up vote 5 down vote accepted

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

share|cite|improve this answer
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! – brainail 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, 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.

share|cite|improve this answer
Thank you for your made work! This is useful in some way. – brainail 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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