Prove that a critically $2$-connected graph has a vertex of degree $2$ Prove that a critically $2$-connected graph has a vertex of degree $2$.
Graph $G=(V,E)$ is critically $k$-connected, if it is $k$-connected and for each vertex $v$ in $V$, graph $G-v$ is $(k-1)-connected$.
I have no idea how to prove it, give some clue please!
Thanks!
 A: You can use the fact that any $2$-connected graph is obtained from a cycle by adding repeatedly new paths between two already existing vertices. If your graph is a cycle, then obviously every vertex has degree $2$. Otherwise, the graph is obtained from a cycle by a path adding process. If the last added path is of length at least $2$, then it contains a vertex of degree $2$ and we are done. Otherwise, the last added path is an edge, whose removal gives us a $2$-connected graph, a contradiction since the original graph is critically $2$-connected.
A: This reply is obviously too late, but in case others are looking at the same or a similar problem, I would first consider how we construct 2-connected graphs. Do you know anything about what operations are sufficient to construct a 2-connected graph? Consider the effect these operations could have on the connectivity of the graph.
Proof:
Let $G = (V, E)$ be any graph obtained from $K_3$ strictly through the operations of edge addition and subdivision. Let $G$ be obtained through $n$ edge additions and $m$ edge subdivisions and let $(o_1,... ,o_{n+m})$ be the sequence of operations performed to obtain $G$.
Base Case: $n + m = 0$. Then, $G = K_3$, which is a critical 2-connected graph because it is 2-connected, however, deletion of any edge results in a 1-connected subgraph of $K_3$.
Inductive Step: $n + m > 0$. Let $G'$ be the graph obtained through the sequence of operations $(o_1,... ,o_{n+m-1})$ of edge addition and subdivision, and assume $G'$ is critical 2-connected. Additionally, since any 2-connected graph can be obtained from $K_3$ through the operations of edge addition and subdivision, we know $G$ is 2-connected (this a theorem you can try proving on your own or finding online if you haven't seen it before). Now we consider two cases:
Case 1: $o_{n+m}$ is edge addition. Let $e$ be the edge added to obtain $G$. The graph $G' = G - e$ obtained through the sequence of operations $(o_1,... ,o_{n+m-1})$ is a 2-connected graph because it is obtained from $K_3$ through a sequence of edge additions and subdivisions and we've assumed it's critical 2-connected. Thus, $G'$ is a 2-connected graph, which means $G$ is not critical 2-connected. Hence, we consider our next case.
Case 2: $o_{n+m}$ is edge subdivision. Let $v_i, v_k \in V(G)$ be two vertices such that $\{ v_i, v_k \} \in E(G')$ but $\{ v_i, v_k \} \notin E(G)$ (due to the subdivision operation). Upon the subdivision operation $o_{n+m}$, let $v_j$ be the vertex such that $\{ v_i, v_j \}, \{ v_k, v_j \} \in E(G)$ and $v_j \notin V(G')$. Note that because $v_j$ is a result of subdivision, $deg_G(v_j) = 2$. Suppose the edge $\{ v_i, v_j \}$ is deleted. $G - \{ v_i, v_j \}$ is not 2-connected because subsequent deletion of $v_k$ would result in the deletion of the edge $\{ v_k, v_j \}$ , which would mean $deg_{G - \{ v_i, v_j \} - v_k} (v_j) = 0$, and $\nexists$ a path from any arbitary $v_m \in V(G)$ ($m \neq j$) to $v_j$. Similarly, if we delete $\{ v_k, v_j \}$, $G - \{ v_k, v_j \}$ is not 2-connected because subsequent deletion of $v_i$ would result in the deletion of $\{ v_i, v_j \}$, which would mean $deg_{G - \{ v_k, v_j \}- v_i}(v_j) = 0$. Since $V(G')$ is critical 2-connected by our inductive hypothesis, we also know that deletion of any other arbitrary edge $e$ such that $e \neq \{ v_i, v_j \}, e \neq \{ v_k, v_j \}$ will also result in a graph that is not 2-connected. Thus, the final operation in a sequence of operations $(o_1$, ... , $o_{n+m})$ of edge addition and subdivision to construct a critical 2-connected graph must be edge subdivision. Recall that the operation of subdivision resulted in a vertex $v_j$ where $deg_G(v_j) = 2$.
Thus, any critical 2-connected graph $G$ has at least one vertex with degree $2$.
