1
$\begingroup$

Show that if a graph $G$ is $2-$connected, then for any two vertices $u$ and $v$ there exists a cycle $C$ such that $u, v \in V (C)$

I tried to use the fact that a graph $G$ with at least $3$ vertices is $2-$connected, if and only if for any $u, v \in V$, with $u \neq v$, there are at least $2 (u, v)-$ trajectories that do not have internal vertices in common.

Any suggestions would be great!

$\endgroup$
3
  • 2
    $\begingroup$ This is something of a "first theorem of 2-connected graphs," its proof should be covered in any decent first textbook on the subject. My concern with your understanding, however, is that most of the proof is contained in the fact you've already mentioned ($G$ is 2-connected $\iff$ for every pair of vertices $x, y$, there are internally disjoint $x, y$-paths). What, exactly, are a pair of internally disjoint paths connecting a pair of vertices? $\endgroup$ May 19, 2020 at 23:40
  • $\begingroup$ Yes, $2$-connectedness indeed implies $2$-internally disjoint paths between any pair of vertices. The definition of $2$-connectedness however, is that the graph remains connected even after removing a vertex. Then proving using only first principles that $2$-connectedness implies the existence if $2$-internally disjoint paths between any pair of vertices, is nontrivial. Or at least I found it so! $\endgroup$
    – Mike
    Apr 27, 2022 at 23:26
  • $\begingroup$ So put another way @Paralyzed_by_Time , a good exercise is to please show $2$-connected gives those internally disjoint paths between any 2 vertices using first principles i.e., without citing Menger's Thm and calling it a day. $\endgroup$
    – Mike
    Apr 28, 2022 at 17:28

2 Answers 2

4
$\begingroup$

Main methodology :

Suppose that in your graph, there exists $u,v$ such that there are no cycle $C$ with $u,v \in C$. Take a path from $u$ to $v$ (it must exist because the graph is connected). Then I claim that at least one edge of the path must disconnect $u$ from $v$ (this is what you need to prove) as otherwise it would create a cycle with $u$ and $v$. Therefore the graph is not 2-connected.

$\endgroup$
2
  • $\begingroup$ This Question (which currently has only your Answer) is being used to close some others as duplicates. I'd feel better about that if the outline you gave, which was perfect for the OP, were expanded somewhat to close the circle (pun intended), I'd be happy to upvote and award a bounty if you make that contribution. $\endgroup$
    – hardmath
    Apr 11, 2022 at 14:40
  • 1
    $\begingroup$ ahahaha ^^ I'd be happy to expand this answer, no need for bounty, I'll do it this afternoon. $\endgroup$ Apr 11, 2022 at 23:29
3
+50
$\begingroup$

This is for an undirected graph $G$:

We show that there is a cycle by using induction on $d_G(u,v)$ i.e., the number of edges in the shortest path from $u$ to $v$, without using Menger's Theorem.

We first show that if $d_G(u,v)$ is $1$ i.e., $uy$ is an edge in $G$, then there is a cycle $C$ containing both $u$ and $v$. To this end, we note the following: First of all, if $G$ is $2$-vertex-connected, then $G$ is $2$-edge-connected. In particular, $G \setminus \{uv\}$ is connected. So letting $P$ be a path from $u$ to $v$ in $G \setminus \{uv\}$, note that $C=P+\{uv\}$ is a cycle.

So now let $k$ be a positive integer. we now assume the following:

(IH) Let $u$ and $v$ be two vertices in $G$ such that $d_G(u,v) \le k$. Then there is a cycle $C$ containing $u$ and $v$.

We now use this to show the following:

THM 1 Let $v'$ be a vertex such that $d_G(u,v')=k+1$. If (IH) is true, then there is a cycle $C'$ containing $u$ and $v'$.

Then from Thm 1 the result will follow.

Proof of THM 1: There is, as $d_G(u,v')=k$, a path $P=uv_1v_2 \ldots v_kv'$ with $k+1$ edges. Now $d_G(u,v_k)=k$ [and also, $v_kv'$ is an edge in $G$; we will use this for Cases 1 and 2 below], so if (IH) is true, there is a cycle $C$ containing both $u$ and $v_k$. We may also assume that $v' \not \in C$ lest we are already done. Write $C=uy_1y_2 \ldots y_rv_ky_{r+1} \ldots y_su$ for some integers $r$ and $s$, and

  • write $uy_1y_2 \ldots v_k$ the left-side of $C$ and

  • write $v_ky_{r+1} \ldots y_su$ the right-side of $C$.

Then, by the fact that $G$ is $2$-connected, there is a path $P'$ from $u$ to $v'$ that does not contain $v_k$. We consider 2 cases:

Case 1: $P'$ intersects $C$ at a point besides $u$. Then writing $P'=v'u'_1u'_2u'_3 \ldots u'_qu$ [for some integer $q$], let $i$ be the smallest integer such that $u'_i$ is in $C$. Then none of $u'_1,\ldots, u'_{i-1}$ is in $C$. Just as crucially, $u'_i$ is distinct from $v_k$.

  • Then if on the one hand $u'_i$ is in $\{y_1,y_2, \ldots, y_r\}$ say $u'_i=y_j$; $j \in \{1,2,\ldots, r\}$, then let $C'$ be the cycle

$$C' = \underbrace{uy_1 \ldots y_j}_{{\substack{\text{from $u$} \\ \text{up the left-side} \\ \text{of $C$ to} \\ \text{$y_j=u'_i \in P'\cap C$}}}} \ \underbrace{u'_{i-1} \ldots u'_1v'}_{\substack{\text{then $P'$ from $u'_iu'_{i-1}$} \\ \text{to $v'$}}}\ \underbrace{v_ky_{r+1} \ldots y_su}_{\substack{\text{then} \\ \text{$v'v_k$ then down} \\ \text{the right-side of $C$}\\ \text{back to $u$}}}.$$

  • If on the other hand $u'_i$ is in $\{y_{r+1},\ldots, y_s\}$ say $u'_i=y_j$ for some $j \in \{r+1,\ldots, s\}$, then let $C'$ be the cycle

$$C' = \underbrace{uy_s \ldots y_j}_{{\substack{\text{from $u$} \\ \text{up the right-side} \\ \text{of $C$ to}\\ \text{$y_j=u'_i \in C\cap P'$}}}} \ \underbrace{u'_{i-1} \ldots u'_1v'}_{\substack{\text{then $P'$ from $u'_iu'_{i-1}$} \\ \text{to $v'$}}}\ \underbrace{v_ky_{r}y_{r-1} \ldots y_1u}_{\substack{\text{then} \\ \text{$v'v_k$ then down} \\ \text{the left-side of $C$}\\ \text{back to $u$}}}.$$

Note that $C'$ indeed is a cycle containing both $u$ and $v'$, using the fact that $u_i$ and $v_k$ are distinct vertices, and $u_1,\ldots, u_{i-1}$ are not in $C$.

Case 2: $P'$ does not intersect $C$ at a point besides $u$. Then set $$C' = P'+v'v_kv_{r+1} \ldots v_su,$$ i.e., $C'$ is the cycle formed by taking $P'$ from $u$ to $v'$, and then from $v'$ take the edge $v'v_k$ and then go back down the right-side of $C$ back to $u$. Note that $C'$ for this subcase as well indeed is a cycle containing both $u$ and $v'$.

As Cases 1 and 2 exhaust the possibilities, THM 1 follows and thus the intended result.


It is natural to ask if an analog to THM 1 exists for directed graphs. Interestingly, the answer to this is NO as there is a graph $G$ such that both:

  • Between any $2$ vertices $u,v$ there are both (a) $2$ dipaths from $u$ to $v$ that are vertex-disjoint except for the endpoints $u$ and $v$ themselves, and (b) $2$ dipaths from $v$ to $u$ that are vertex-disjoint except for the endpoints $v$ and $u$ themselves.

  • There are also $2$ vertices $u$ and $v$ such that there is no directed cycle containing both $u$ and $v$ simultaneously.

Let $G$ be the graph on $\{v_1,v_2,v_3,v_4,v_5,v_6\}$ where the arcs in $G$ are $v_1v_4, v_4v_1, v_4v_5,v_5v_6$, $v_5v_1$, $v_1v_2,v_2v_3,v_3v_6, v_6v_3, v_6v_2$, $v_3v_5$. $v_2v_4$. Then draw the graph out, and check that

  • Between any $2$ vertices $u,v \in \{v_1,v_2,v_3,v_4,v_5,v_6\}$ there are both (a) $2$ dipaths from $u$ to $v$ that are vertex-disjoint except for the endpoints $u$ and $v$ themselves, and (b) $2$ dipaths from $v$ to $u$ that are vertex-disjoint except for the endpoints $v$ and $u$ themselves.

  • There is no directed cycle containing both $v_1$ and $v_6$ simultaneously.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .