# If there is a cycle containing edges $a, b$ and another one containing edges $b, c$, then there is a cycle containing $a, c$

Given a simple undirected connected graph $G$, containing edges $a, b, c$, I would like to prove that if $\exists$ a cycle $C_1$ that contains edges $a$ and $b$ and a cycle $C_2$ containing edges $b$ and $c$, then there must be a cycle $C_3$ that contains edges $a$ and $c$.

Let $a=\{u_a,v_a\}, b=\{u_b,v_b\}, c=\{u_c,v_c\}$.

I have decomposed the cycles as follows:

$C_1=\{u_a,a,v_a,(\text{Part A}),u_b,b,v_b,(\text{Part B}),u_a\}$

$C_2=\{u_b,b,v_b,(\text{Part C}),u_c,c,v_c,(\text{Part D}),u_b\}$

If the cycles don't intersect, then the following works:

$C_3=\{u_a,a,v_a,(\text{Part A}),u_b,b,v_b,(\text{Part C}),u_c,c,v_c,(\text{Part D}),u_b,b,v_b,(\text{Part B}),u_a\}$

However this does not work if the parts $A$ or $B$ share vertices with parts $C$ or $D$.

How can I prove that the initial claim is true in all cases? Thanks!

• So obviously true... yet difficult to prove! – David G. Stork Sep 15 '17 at 18:41

## 1 Answer

Using the OP's notation:

Consider cycle $C_1$ including edges $a$ and $b$. Without loss of generality, we can say there is a chain (linear graph, Part $A$) from vertex $v_a$ to $u_b$ and a chain (linear graph, Part $B$) from vertex $u_a$ to $v_b$. For simplicity we include the end vertices, $v_a$ and $u_b$ in Part $A$ and vertices $u_a$ and $v_b$ in Part $B$.

Because there is a cycle $C_3$ including edge $c$ and edge $b$, that cycle must pass through $u_b$ and $v_b$. Thus the cycle must pass through at least one vertex in Part $A$ and one vertex in Part $B$.

Call $u_1$ the vertex on $C_3$ on Part $A$ that is closest to $v_a$. One path from $u_1$ leads to edge $c$ without passing through $b$. Call that path Part $C$. (Without loss of generality we can assume Part $C$ includes $u_c$.)

Call $u_2$ the vertex on $C_3$ on Part $B$ that is closest to $u_a$. One path from $u_2$ leads to the other vertex of edge $c$ (i.e., $v_c$). Call the path from $u_2$ to $v_c$ Part $D$.

A cycle containing $a$ and $c$ is thus:

• edge $a$
• From $v_a$ to $u_1$ along a portion of Part $A$
• From $u_1$ to $u_c$ along portion of Part $C$
• edge $c$
• From $v_c$ to $u_2$ along a portion of Part $D$
• From $u_2$ to $u_a$ along a portion of Part $B$

Informally, we're finding the vertex in $C_3$ on Part $A$ closest to $a$ on "one side" (i.e., to $v_a$) and likewise the vertex in $C_3$ closest to $a$ on the "other side" (i.e., to $u_a$), and then replacing the path from $u_1$ to $u_2$ in $C_3$ with the linear path from $u_1$ to $v_a$ to $a$ to $u_a$ to $u_2$.