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?
Euler graph having simple cycles
5
$\begingroup$
graph-theory
-
0@Henry: I guess it is at least two, rather than more than two... – 2011-03-14
2 Answers
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?