
Applied Math Applied Math Forum 
 LinkBack  Thread Tools  Display Modes 
December 13th, 2015, 05:37 AM  #1 
Newbie Joined: Dec 2015 From: Germany Posts: 1 Thanks: 0  Graph theory: Prove that each cycle has minimum length of 5
How do I prove that each cycle in this graph has a minimum length of 5? 
December 29th, 2015, 11:58 AM  #2 
Member Joined: Jun 2009 Posts: 83 Thanks: 1 
Hi, I think it suffices to prove it for selected fixed vertex v0  because the graph is symmetric (automorphism is eg. every mapping sending vertex v to vertex not adjacent with v). And checking it for v0 is easy  it can be seen that cycle of length 3 and 4 doesn't exist. 
March 22nd, 2016, 09:33 AM  #3 
Newbie Joined: Mar 2016 From: Slovenia Posts: 1 Thanks: 0 
How do I prove that every circulant of girth at least 4 and with degree 4 is nonplanar?


Tags 
cycle, graph, length, minimum, prove, theory 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How to prove graph also has a cycle of length a + b2.  Jas17  Computer Science  1  November 8th, 2015 07:38 PM 
Prove that a cycle of length n in Sk has order n  Elladeas  Abstract Algebra  1  February 4th, 2012 11:16 AM 
Graph theory proof (uniqueness of minimum spanning tree)  aeromantang  Applied Math  3  December 28th, 2011 10:34 AM 
Prove a limitgraph theory  mathdude  Applied Math  0  December 1st, 2010 04:07 PM 
Prove G contains a cycle of length at least k+1  cxc001  Applied Math  1  October 1st, 2010 02:21 AM 