2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Batominovski Nov 19 '18 at 21:16
  • $\begingroup$ @Batominovski Here I'm referring to 2-vertex-connected. $\endgroup$ – Thomas Nov 19 '18 at 21:25
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – aleph_two Dec 22 '18 at 5:48

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.