2
$\begingroup$

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!

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

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$.

enter image description here

$\endgroup$

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.