A graph $G$ is said to be $k$-connected (or $k$-vertex connected, or $k$-point connected) if there does not exist a set of $k-1$ vertices whose removal disconnects the graph.

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

My proof :
G is 2-connected. So, $G-v$ is connected. If we show that $G-v-u$ is connected, the problem is solved.
According to Menger's Theorem, if a graph is $k$-connected, there exists $k$ internally disjoint paths between each two vertices. So, here, in this question, there exists 2 disjoint paths between every two vertex.
Every path in $G$ is one of these two types:

1) The path $P$ between two arbitrary vertices like $a,b$ contains $u$.
2) $P$ doesn't contain $u$.

Case 1 : When we delete $u$, there still exists a path between $a,b$ ( According two Menger's theorem, because our graph is 1-connected) So, we take the path and the graph remains connected.
Case 2 : We don't need $u$ when traveling from $a$ to $b$. So, Nothing happens to $P$ when we remove the vertex $u$.

Is this proof correct ? Or can you prove a better proof?

I also found this proof which i don't understand :proof
Thanks in advance.

  • $\begingroup$ Your proof seems to show that the removal of any two neighbouring vertices should work, which is not the case $\endgroup$ Apr 29 '16 at 13:01
  • $\begingroup$ @HagenvonEitzen Can you help me with the proof? even a hint is helpful sir :) $\endgroup$
    – Perceptual
    Apr 29 '16 at 13:02
  • $\begingroup$ did you ever figure this out? @ArmanMalekzadeh $\endgroup$ Feb 27 '18 at 5:19

Think of the blocks of $G-v$. Assume it has a leaf block B (what about the other case?). How do the two internally disjoint paths connecting an "internal" vertex of B with some vertex in another block look like?

  • $\begingroup$ please explain it more ! i don't understand what you wrote $\endgroup$
    – Perceptual
    Apr 30 '16 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.