# Show any two edges in a 2-connected graph lie on a cycle

So I found some proofs on any two vertices would lie on a cycle, but stuck on dealing with edges. We can say any two edges are connected, but does that just imply they will be on a common cycle?

• Which kind of $2$-connectedness are you referring to: $2$-edge-connected or $2$-vertex-connected? I would guess that $2$-edge-connected is what you are aiming for, but I can't say for sure. – Batominovski Nov 19 '18 at 21:16
• @Batominovski Here I'm referring to 2-vertex-connected. – Thomas Nov 19 '18 at 21:25

Although this question is already a few months old, I will post my (hopefully working) answer, as I was searching for it for a long time as well.

We can extend the graph G by adding two vertices a, b in the middle of the edges wanted in one cycle. This does not change our graph being 2-connected, but now we can reduce the question of finding a cycle containing the two edges in G to the question of a cycle containing a and b in G'.

Let $$G = (V, E)$$ graph, $$|V| \ge 3$$. Suppose that there exists an edge $$e = (u, v) \in E$$ such that $$e$$ does not lie on a cycle. Then every path from $$u$$ to $$v$$ must contain $$e$$ (1). If $$u$$ or $$v$$ are a leaf, then removing the vertex that connects the leaf from the rest of the graph makes the leaf disconnected (!). Otherwise, define the following partition of $$G$$ without $$e$$:

$$G_u = (V_u, E_u) \quad \quad G_v = (V_v, E_v)$$

where $$V_u = \{w \in V |$$ there is a path from $$w$$ to $$u$$ that does not contain $$e\}$$, $$E_u = \{(w, t) \in E | w, t \in V_u\}$$ and $$V_v$$, $$E_v$$ are defined analogously (2). If we remove $$u$$ or $$v$$ from the graph, then we are also removing $$e$$. Note, however, that if we remove $$e$$, then there is no path to go from any $$w \in G_u$$ to any $$t \in G_v$$. In other words, the graph becomes disconnected (!).

Notes:

(1) Suppose that there exists a path from $$u$$ to $$v$$ that does not contain $$e$$. Then we can join this path to $$e$$ to form a cycle, but by doing so we are showing that $$e$$ lies on a cycle (!).

(2) It is easy to show that $$G_u$$ and $$G_v$$ are disjoint.

• Hi there! I'm afraid I don't understand how this answers the question; it seems you are showing that any single edge in a 2-connected graph exists on some cycle, but the question is to show that any two edges, there's a single cycle that contains both. – aleph_two Dec 22 '18 at 5:48