5
$\begingroup$

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?

  • 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?2011-03-14
  • 0
    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...2011-03-14
  • 0
    @Henry: I guess it is at least two, rather than more than two...2011-03-14

2 Answers 2

2

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

1

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?