Graph theory: Prove that each cycle has minimum length of 5

Has

New member
Joined
Dec 13, 2015
Messages
1
Hi, I'm a computer science student and I'm stuck with following problem:

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

The following graph G is given:

attachment.php


I first have drawn some cycles in order to see whether indeed the minimum length is equal to 5. Then I was thinking in terms of planarity. Maybe if I see that G is planar, I can then draw an equivalent graph G' and see what is the minimum length of the graph. When I tested on planarity, I saw that G is not planar and therefor I'm now stuck with it.

Thank you.
 

Attachments

  • 2qly7oh.png
    2qly7oh.png
    2 KB · Views: 20
Last edited:
How can I prove that indeed each cycle of this graph G has a minimum length of 5?

The following graph G is given:

attachment.php
What are your thoughts?

Please share your work with us ...even if you know it is wrong

If you are stuck at the beginning tell us and we'll start with the definitions.

You need to read the rules of this forum. Please read the post titled "
Read before Posting" at the following URL:

http://www.freemathhelp.com/forum/th...Before-Posting
 
Top