Math Is Fun Forum

Has

Member

Registered: 2015-12-13

Posts: 1

Graph theory: prove that each cycle in graph has minimum length of 5

Hi, I'm stuck with this proof.

I have a graph G

How can I prove that each cycle in this graph has indeed a minimum length of 5?

Thank you very much!

Bob

Administrator

Registered: 2010-06-20

Posts: 10,643

Re: Graph theory: prove that each cycle in graph has minimum length of 5

hello Has,

Welcome to the forum.

I don't know much graph theory and I got nothing that would help from an internet search but here's a suggestion.  If you've got access to a matrix manipulator you could give it a try and see.

Simple example:  Take the triangle ABC as a simple graph. The node to node incidence matrix is

This shows that there is one route from A to B and no routes from A to A, etc.

If you square the matrix you get the ways of going from one point to another via an intermediary point.

The 2-cycles show up clearly.

So maybe you can construct the 10 by 10 matrix for the graph, let's say it is M, and then compute M^2, M^3 etc .  If I'm right the first non zeros on the leading diagonal will only show at M^5

EDIT: Sorry.  Not quite there.  I've just tried it for a more complicated graph and A to B followed by B to A messes up my idea.  Wonder what happens if the routes are one way?

FURTHER EDIT:  That worked for a 'directed' graph.  ie. all routes one-way.  So does that help?

Last try for now:  There's a matrix calculator at https://www.mathsisfun.com/algebra/matr … lator.html

It's easy to show that A^2 gives 2-cycles that are all of the form A to B followed by B to A. 

A^3 has no cycles.

A^4 has 15.  So it is only necessary to show these all involve repetition of a point and you're done, since it is easy to show that some 5-cycles exist.

Bob

Last edited by Bob (2015-12-14 01:13:47)

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob