I'm trying to solve the following question:
Let G be graph on n ≥ 4 vertices with 2n − 2 edges. Prove that G has two cycles of equal length.
I have reached the following observations:
- If I try and prove this by induction, during the induction step I have a graph of n vertices and if I remove the minimal-degree vertex it's easy to see that if it has 2 or less edges, then the resulting graph is a graph of n-1 vertices and at least 2(n-1)-2 edges, so by the induction assumption there are two cycles of equal length. However I still need to prove that if the minimal degree in the original n-vertices graph is larger than 2, then this means it is still possible to find two equal length cycles (it's no longer possible to remove a vertex and keep the required amount of edges).
- If a graph has a minimal degree of 3, then it has a cycle with a chord - perhaps this could help me here, alongside with the induction idea?
- If the minimal degree is 3 I believe this means that there must be a cycle of length 4 (at least one). Maybe it's possible to look at this cycle and do something with it (maybe removing it...?)
Any help would be appreciated as I am currently a bit stuck.