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

Question

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!

Answer 1

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.

Answer 2

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.