My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum

LinkBack Thread Tools Display Modes
December 13th, 2015, 05:37 AM   #1
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?

Has is offline  
December 29th, 2015, 11:58 AM   #2
Joined: Jun 2009

Posts: 83
Thanks: 1

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.
honzik is offline  
March 22nd, 2016, 09:33 AM   #3
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 non-planar?
alja is offline  

  My Math Forum > College Math Forum > Applied Math

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

Copyright © 2019 My Math Forum. All rights reserved.