Show that a $2$-connected graph with minimum degree greater than or equal to $3$, has a vertex $v$ such that $G-v$ is $2$-connected

Question

Assume that $G$ is a $2$-connected graph with $δ(G)≥3$. Show that there is a vertex $v\in G$ such that $G−v$ is $2$-connected.

This question is a duplicate, I'm aware. However as the author of that other question said when he posted an answer, his proof is not based on well known theorem from textbooks. I'd appreciate if someone could provide a proof based on such theorems, or maybe point me to the right direction on how I could prove this myself.

Answer 1

All we need is the result that a graph is $2$-connected if and only if it has an (open/proper) ear decomposition. This is a way of building a graph, starting with a cycle. We pick two distinct vertices in the graph built so far, and add a path between them, of any length. If the path has any internal vertices, then those are completely new to the graph.

A graph can have many ear decompositions. Most of those will not help. We'd like to find one which ends by adding a length-$2$ ear (with one extra vertex $v$) and then some length-$1$ ears (edges) with one endpoint at $v$. If we find such an ear decomposition, we can delete $v$. $G-v$ is $2$-connected: its ear decomposition is just the ear decomposition of $G$, stopped before we add $v$.

To find such an ear decomposition, out of all the ear decompositions $G$ might have, pick one such that:

1. The last ear added which has length $>1$, call it $E^*$, is as short as possible;
2. Subject to 1, the number of ears of length $1$ added after $E^*$ is as small as possible.

I claim that this ear decomposition has the property we want.

Suppose that $E^*$ has more than one vertex: it is a path $v_0, v_1, \dots, v_k$ where $v_1, \dots, v_{k-1}$ are new. Right after we added $E^*$, the vertices $v_1, \dots, v_{k-1}$ have degree $2$, and $G$ has minimum degree $3$, so those vertices are going to get extra edges added to them later. There's two cases:

• We add an edge $v_i w$, where $w$ is not on $E^*$. Then we could have added the vertices of $E^*$ in two adding-an-ear steps. We could have added the ear $v_0, v_1, \dots, v_i, w$ and then $v_i, v_{i+1}, \dots, v_k$, which is a better ear decomposition by our measure unless $i=k-1$ and that last ear has no internal vertices. In that case, we could also have added the ear $w, v_i = v_{k-1}, v_k$ and then the ear $v_0, v_1, \dots, v_{k-1}$, which is a better ear decomposition by our measure.
• We add an edge $v_i v_j$, where $j > i+1$. Then instead of adding ear $E^*$, we could have added the ear $v_0, v_1, \dots, v_i, v_j, \dots, v_k$ followed by the ear $v_i, v_{i+1}, \dots, v_j$. This is a better ear decomposition by our measure.

Either way, we contradict the extremal property of the ear decomposition we chose. So $E^*$ just has one vertex $v$.

After we add $E^*$, all ears of length $1$ we add must be incident to $v$. Otherwise, we could have added them earlier, and had a better ear decomposition. Therefore, $G-v$ has an ear decomposition: the ear decomposition we had before we added the ear $E^*$. Therefore, $G-v$ is $2$-connected.