Does a 2-connected graph, say $G$ have a vertex, say $v$, such that $G-v$ is still 2-connected?

323 Views Asked by At

I have been trying to solve this problem for some days. Then, I put the problem here, and it is here for some days. I appreciate it if someone even give me some hint.

Assume that $G$ is a 2-connected graph with $\delta(G)\geq 3$. Show that there is a vertex like $v$ that $G-v$ is 2-connected.

$\bullet$ Do I need to propose an algorithm to find such a vertex to solve the problem? Or, it can be proved in another way?

1

There are 1 best solutions below

0
On BEST ANSWER

Well, as I have not found still a proper answer, I am writing the answer obtained from the paper which suggested by Leen Droogendijk. First, we are to see a definition and a theorem, and then the proof is implied by contradiction.

Definition. A graph $G$ is named critically $n-$connected if $\kappa(G)=n$ and $\kappa(G-v)=n-1$ for every vertex $v \in G$.

Theorem. If $G$ is a critically $n-$connected graph with $n\geq 2$, then $\delta(G)<\frac{3m-1}{2}$ and the number $\frac{3m-1}{2}$ cannot be improved.

Now, the proof can be easily gained on the contradiction. Assume that there is no such a $v\in G$ as said in the problem. Thus, for each $v∈V$, the sub graph $G−v$ is not a $2-$connected, and so one can conclude that the graph is a critically $2-$connected (see the definition), and hence according to the theorem, it is implied that $δ(G)<5/2$ which contradicts the assumption of $δ(G)≥3$.

$\bullet$ Although it is a proof, but I need a proof based on the well known results in the text books. I appreciate it if someone help me this way.