Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

One property of Euler graphs is that if a graph with $n \geq 3$ vertices and more than $n$ edges has an Euler circuit, then it has more than two simple cycles. How can we prove it?

share|improve this question
1  
I am not sure I understand. If you take the graph with 5 vertices A, B, C, D, and E, and 6 edges AB, BC, CA, AD, DE, EA then the edges in that order ABCADEA provide an Euler circuit and there are just two simple cycles ABCA and ADEA. Or does simple mean something else? –  Henry Mar 14 '11 at 23:45
    
This looks like homework (and your past questions add more credence to that supposition). Why don't you show what you have tried? It is usually bad form to post homework questions without showing indications of having put in some effort... –  Aryabhata Mar 14 '11 at 23:46
    
@Henry: I guess it is at least two, rather than more than two... –  Aryabhata Mar 14 '11 at 23:48
add comment

2 Answers

up vote 2 down vote accepted

Hint (for atleast two, see Henry's comment): Consider the vertex with the maximum degree.

share|improve this answer
add comment

Hints: Consider a Euler circuit as you know there is at least one.

  • Can you split the circuit into cycles?
  • Where?
  • Why?
  • Does that leave you with simple cycles?
  • If not, what can you do to create simple cycles?
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.