Let $v$ be a vertex of a 2-connected graph $G$. Prove that $v$ has a neighbor $u$ such that $G − u − v$ is connected.

Question

Let $v$ be a vertex of a 2-connected graph $G$. Prove that $v$ has a neighbor $u$ such that $G − u − v$ is connected.

I'm not sure I understood that prove. Please anyone can explain me that ? Prove that in a 2-connected graph like G which has the vertex $v$, $v$ has a neighbor $u$ such that $G-v-u$ is connected

Thanks!

Answer 1

Let $u_1$ be any neighbor of $v$. If $G - v - u_1$ is connected then we have found our vertex. If $G - v - u_1$ is disconnected, look at the set of components. If any component contains no neighbors of $v$, then $G-u_1$ must actually be disconnected, which is a contradiction. So we may assume all components contain neighbors of $v$. Choose some such component, and let $u_2$ be one of the neighbors of $v$ lying in it.

Now consider $G - v - u_2$. If this is connected then again we have found our vertex. If it is disconnected, look at the set of components, which again must each contain neighbors of $v$. Choose some component that does NOT contain $u_1$, choose a neighbor of $v$ in it, and call that neighbor $u_3$.

The idea is that we repeat this process, and when we look at the components of $G - v - u_k$ we can observe that $u_1 \cdots u_{k-1}$ must all actually lie in the same component. Thus, we never end up in a circle, and the process must eventually terminate. When it terminates, we have found the desired $u$.

Answer 2

Take a vertex $v$ of $G$, and let $U:=N(v)$ be the set of neighbors of $v$, then let $T$ be the smallest connected subgraph of $G-v$ containing all vertices in $U$. Then $T$ is a tree as you can remove edges on the any cycle to make it a tree. Also, all leafs of $T$ are vertices in $U$ as otherwise you can just remove the leaf to make a smaller connected subgraph containing all vertices in $U$. Take $u$ be any leaf of $T$, and suppose $G-v-u$ is not connected. Then let $C$ be a component of $G-v-u$ not containing $T-u$. But then $C$ does not contain any neighbors of $v$, so $G-v$ is disconnected contradicting 2-connectivity of $G$.