If an undirected graph contains two cycles of lengths a, b respectively, that have exactly one edge in common. How can I prove that the graph also has a cycle of length
a + b2.
How to prove graph also has a cycle of length a + b2.

 Posts: 1
 Joined: Sat Oct 31, 2015 8:57 am
Re: How to prove graph also has a cycle of length a + b2.
If you draw a sketch of the situation, it will become really obvious.
_{Jaap's Puzzle Page}
Re: How to prove graph also has a cycle of length a + b2.
A little bit more formally:
Let e(n1,n2) be the common edge.
then there exist 3 paths from n1 to n2 which have no common edges:
Length 1: {e}
Length a1: C_a/e (Cycle a without edge e)
Length b1: C_b/e
Lemma 1: C_a/e has a1 edges
C_a/e contains not e
C_a = C_a/e + e
e has Length 1
Lemma 2: Combining two Paths from n1 to n2 with no common edges result in a circle
Combining paths (with no common edge) n1 to n2 with length a and n2 to n3 with length b will result in a path n1 to n3 with length a+b
In undirected graphs, a path n1 to n2 is a path n2 to n1 too.
So combining n1 to n2 and n2 to n1 will result in a path n1 to n1.
And a path n1 to n1 is a circle.
Combining C_a/e and C_b/e will result in a circle with length a1 + b1 = a+b2
Let e(n1,n2) be the common edge.
then there exist 3 paths from n1 to n2 which have no common edges:
Length 1: {e}
Length a1: C_a/e (Cycle a without edge e)
Length b1: C_b/e
Lemma 1: C_a/e has a1 edges
C_a/e contains not e
C_a = C_a/e + e
e has Length 1
Lemma 2: Combining two Paths from n1 to n2 with no common edges result in a circle
Combining paths (with no common edge) n1 to n2 with length a and n2 to n3 with length b will result in a path n1 to n3 with length a+b
In undirected graphs, a path n1 to n2 is a path n2 to n1 too.
So combining n1 to n2 and n2 to n1 will result in a path n1 to n1.
And a path n1 to n1 is a circle.
Combining C_a/e and C_b/e will result in a circle with length a1 + b1 = a+b2