0
$\begingroup$

$G$ is $2$-vertex-connected graph if and only if every $2$ vertices from $G$ lie on a simple cycle.


$\implies$

If $G$ is $2$-vertex connected graph it means for every $ v \in V(G), \deg(v) \ge 2 $ because if exist any $ v_1 $ and $ \deg v_1 = 1 $ then we can erase neighboring vertex and graph will not connected so won't be 2-vertex connected. So if $ v \in V(G), \deg(v) \le 2 $ then it exist cycle. $ \deg_v \ge 2 $ so if we start in $v$ we have to back to this vertex.

$\impliedby$ I don't know.

$\endgroup$
1
  • $\begingroup$ What definition of two-connected are you using? $G$ is connected and after removing any single vertex from $G$ it is still connected? Specifically, is $K_2$ 2-connected? $\endgroup$ Jun 30, 2013 at 11:33

2 Answers 2

2
$\begingroup$

I think your forwards implication is a little vague.

Take two vertices $u$ and $v$. We want to find a simple cycle containing them. As you've noted, each vertex must have at least two neighbours. So let $u_1$ and $u_2$ be two neighbours of $u$, and consider the graph we get from deleting $u$. We know by assumption that it is still connected, so we can find paths from $u_1$ to $v$ and $u_2$ to $v$. Joining these together will give us a simple cycle containing $u$ and $v$, so we're done — provided the two paths don't intersect. Can every such path have an intersection? Explain why not.

For the reverse implication, take a vertex $x$ which we want to delete, and two vertices $a$ and $b$ which we want to connect in the resulting graph. Using the fact that we can conjure up a simple cycle containing $a$ and $b$, show that we can get a path in $G \setminus \{ x \}$ containing $a$ and $b$.

$\endgroup$
1
$\begingroup$

There is an easier way to justify the forward implication.

We know that with the help of Menger's Theorem, that if a graph is 2-vertex connected, then there exists two disjoint paths for any two vertices u and v of the vertex set of the Graph. If we choose any two vertices in the graph and pick a path P(u,v) and Q(v,u), then we have a cycle given by [P(u,v)Q(v,u)] that contains u and v.

$\endgroup$

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.