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?

  • 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?