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

 Computer Science Computer Science Forum

 October 31st, 2015, 12:53 AM #1 Newbie   Joined: Oct 2015 From: India Posts: 4 Thanks: 0 How to prove graph also has a cycle of length a + b-2. 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.
 November 8th, 2015, 07:38 PM #2 Newbie   Joined: Nov 2015 From: Logan, UT Posts: 9 Thanks: 5 Math Focus: Stochastic processes My recommendation to start this proof is to examine a particular case -- say, a=3 and b=4. Draw a cycle length 3 and a cycle length 4 where the cycles have exactly one edge (two nodes) in common. Now that you have drawn a picture, can you spot a cycle with length 3+4-2=5? Sure, a cycle length 5 involves walking around the outside of the whole figure. So does this always work when two cycles share exactly one edge? Suppose the edge shared between the two cycles connects nodes X and Y. How many edge steps must you take to walk from X to Y along the cycle length a? Now, how many steps are required to get back to X from Y around cycle length b? The total number of steps to get from X to X the long way is a+b-2. Q.E.D.

 Tags cycle, discrete mathe, graph, graphs, length, prove

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Elladeas Abstract Algebra 1 February 4th, 2012 11:16 AM nicolodn Algebra 1 October 9th, 2010 04:54 PM cxc001 Applied Math 1 October 1st, 2010 02:21 AM ry. Applied Math 0 April 13th, 2010 05:45 AM nicolodn Calculus 1 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top