3
$\begingroup$

Show that for any two edges of a 2-connected graph, a cycle exists containing both of them.

Here's what I have tried so far:

Lemma. A graph $G$ is 2-connected if and only if every two vertices are contained in a cycle.

Attempt: Let $e_1=\{v_1,v_2\}$, $e_2=\{w_1,w_2\}$ be two edges of $G$. By lemma, there is a cycle $C_1$ containing $v_1,w_1$ and a cycle $C_2$ containing $v_2,w_2$. Denote the two paths from $v_1$ to $w_1$ in $C_1$ as $p_1$ and $p_2$ and similarly set $r_1$, $r_2$ for the two paths in $C_2$. Then divide the problem into different cases:

Case 1: Neither $p_1$ nor $p_2$ intersects $r_1$ or $r_2$.

Case 2: Only one of $p_1$ and $p_2$ intersects $r_1$ or $r_2$.

Case 3: Both intersect $r_1$ or $r_2$.

For the first two cases it is easy to show that such cycle exists by just picking one path from each $C_1$ and $C_2$. But the third case is a lot complicated so I believe there should be a much nicer way to approach this problem. Any idea?

$\endgroup$
2
$\begingroup$

Hint:

  • If $e$ belongs to any cycle, then subdividing it (creating a vertex in the middle) doesn't break 2-connectivity.

I hope this helps $\ddot\smile$

$\endgroup$
2
  • $\begingroup$ sorry I am still unsure how to proceed with this. Why would I subdivide one edge? Thank you very much. $\endgroup$
    – user112358
    Oct 25 '16 at 10:03
  • $\begingroup$ @Lewis You asked about a nicer way to prove your claim. $\endgroup$
    – dtldarek
    Oct 25 '16 at 11:19

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.