How to prove graph also has a cycle of length a + b-2.

Arrangements, sorting, packing, partitions, critical path analysis, networks, graphs, ...
Post Reply
techno_user
Posts: 1
Joined: Sat Oct 31, 2015 8:57 am

How to prove graph also has a cycle of length a + b-2.

Post by techno_user » Sat Oct 31, 2015 9:00 am

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 + b-2.

User avatar
jaap
Posts: 538
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: How to prove graph also has a cycle of length a + b-2.

Post by jaap » Sat Oct 31, 2015 6:43 pm

If you draw a sketch of the situation, it will become really obvious.

v6ph1
Posts: 114
Joined: Mon Aug 25, 2014 6:14 pm

Re: How to prove graph also has a cycle of length a + b-2.

Post by v6ph1 » Sat Oct 31, 2015 11:10 pm

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 a-1: C_a/e (Cycle a without edge e)
Length b-1: C_b/e

Lemma 1: C_a/e has a-1 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 a-1 + b-1 = a+b-2
Image

Post Reply