Prove that there exists a edge $e$ in a 2-connected graph with degree of each vertex $\ge 3$ on removal of which the graph $G'$ still remains 2-connected.
I cant seem to reason a proof by induction, since what would be the variable on which I would do induction on. This seemed more like a construction or contradiction proof to me.
In contradiction approach, how do you proceed to prove the existence on one such edge. As in I know how to apply proof by contradiction to find that there exists a property for all edges or something similar but how do you prove the existence of one such edge. (I know I can take the negation of the statement and try to prove it but it gave me no progress)
In construction approach, let us say we take the graph which only minimally satisfies this condition, i.e. degree of each vertex is 3 and it is 2-connected, then we try to find an edge satisfies this, by saying that if it does not remain 2-connected, then we can try with other edge but finally arrive at a conclusion that this edge must be left to satisfy this condition. But I cant seem to find a way out of this also.
P.S. Menger's Theorem might be helpful
CLEAN PROOF
We'll try to prove the contrapositive:
Solution:
We know that any 2-connected graph is obtained from a cycle by adding repeatedly new paths between two already existing vertices. If our graph is a cycle, we are done. Otherwise, it’s obtained from a cycle in a path-adding process. If the last added path is of length at least 2, we have a vertex of degree 2 and we are done. If not, then the last path is an edge whose removal leaves a 2-connected graph. The latter can’t happen as we deal with a critical 2-connected graph
(Courtesy: Karthik)
NOT CLEAN PROOF
Let's say that if we remove $e$ then $G-e$ becomes 1-connected. Thus, there exists a cut vertex $v$ with 2 components $C_1$ and $C_2$.
Note that only two components can exist, since if there are say $x$ components, then to make graph connected, we would have to add $x-1$ edges but we removed only one.
Also between $C_1$ and $C_2$, only one edge $e$ can exist, since otherwise even on removal of $e$ graph will remain 2-connected.
Therefore, there would be one extra edge from $v$ to $C_1$ or $C_2$. If there are more, then we can remove them (slight doubt). Let us assume, that $v$ has two edges to $C_2$ and one to $C_1$. Let $e$ connect to $a$ in $C_1$ and $f$ connect to $v$ to $b$ in $C_1$. ($a\ne b$ since cut vertex otherwise)
Now we try to prove by induction on number of vertices + edges. So if we remove $C_2$ and $v$ and replace that with a direct edge from $a$ to $b$, we have kept the same conditions for the new graph $G' = C_1\cup \{a,b\}$, i.e. $\delta(v) \ge 3$ and 2-connected. Now if this is valid we can remove one edge from $G'$. If that edge is not ${a,b}$ then our work is done by induction since we would be able to add back $C_2$ and $v$ to $G'-some\ edge$ and get back the original graph - an edge, still keeping it 2-connected. But if $G-\{a,b\} = C_1$ is 2-connected then we have the following case...
$C_1$ is 2-connected. Hence we prove that we can remove one edge from it and keep it connected. So if we prove that for any 2-connected $C_1$ we can remove an edge such that there are always 3 independent paths $\{a,..,x\}, \{x,..,y\}\ \&\ \{y,..,b\}$ for any $x,y$ then we are done because in original graph $G$ we can remove one edge from $C_1$ and then also it shall be 2-connected. We prove this by induction on number of vertices. Since degree of each vx is at least 3, a has at least 2 points which it is connected to in $C_1$ and we will try to remove that (this has 2 cases, but can be proved easily on paper with diagrams). Thus we are done
OLD
NOTE: THIS PROOF IS NOT COMPLETE
Let's say that if we remove $e$ then $G-e$ becomes 1-connected. Thus, there exists a cut vertex $v$ with 2 components $C_1$ and $C_2$.
Note that only two components can exist, since if there are say $x$ components, then to make graph connected, we would have to add $x-1$ edges but we removed only one.
Also between $C_1$ and $C_2$, only one edge $e$ can exist, since otherwise even on removal of $e$ graph will remain 2-connected.
Therefore, there would be one extra edge from $v$ to $C_1$ or $C_2$, since $\delta(v) \ge 3$. Hence we can remove it and keep graph 2-connected. (UPDATE: not entirely true, multiple cases exist and I cant solve some of them)
(Courtesy: Swapnil)