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!

  • 1
    @Azoo This is example: h$t$tp://i.imgur.com/Zfcfg.png. Please remove the central verte$x$.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
    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.

  • 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