18
$\begingroup$

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!

Thanks!

  • 0
    Where did you found this problem?2012-09-29
  • 0
    @Azoo This is problem from the teacher's book from the University. Is something wrong with this problem?2012-09-29
  • 0
    No its just that I never heard of any similar problem.2012-09-29
  • 0
    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?2012-09-29
  • 0
    @Azoo Yes, I know the example.2012-09-30
  • 1
    @Azoo This is example: http://i.imgur.com/Zfcfg.png. Please remove the central vertex.2012-09-30

2 Answers 2

6

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

  • 0
    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.2012-10-18
  • 1
    @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.2012-10-18
  • 0
    Thank you for the link. Gorgeous skill. Thanks for your help!2012-10-19
1

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 https://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.

  • 0
    Thank you for your made work! This is useful in some way.2012-10-14
  • 0
    “all its neighbors are in the graph as well” : you mean in the path as well, right ?2012-10-16
  • 2
    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.2012-10-17