My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
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 + 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.
Jas17 is offline  
 
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.
mathinsider is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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 semi-log 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 semi-log cycle graph paper ? nicolodn Calculus 1 December 31st, 1969 04:00 PM





Copyright © 2019 My Math Forum. All rights reserved.