
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
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 + b2.
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. 
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+42=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+b2. Q.E.D. 

Tags 
cycle, discrete mathe, graph, graphs, length, prove 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prove that a cycle of length n in Sk has order n  Elladeas  Abstract Algebra  1  February 4th, 2012 11:16 AM 
How to use semilog cycle graph paper ?  nicolodn  Algebra  1  October 9th, 2010 04:54 PM 
Prove G contains a cycle of length at least k+1  cxc001  Applied Math  1  October 1st, 2010 02:21 AM 
digraph: cycle of an even length and coloring the vertices  ry.  Applied Math  0  April 13th, 2010 05:45 AM 
How to use semilog cycle graph paper ?  nicolodn  Calculus  1  December 31st, 1969 04:00 PM 