# Graph theory: cycles

Prove that if two distinct cycles of a graph G each contain an edge e, then G has a cycle that does not contain e.

My approach is since they both have edge e then if we remove edge e from both then connect the two cycles together at vertex a and b which edge e connected to then we would get a cycle. Am I missing something here?

This isn't a homework question, just a question from my textbook.

-
add comment

## 2 Answers

Another approach would be to take the connected component that contains both cycles and observe that in this subgraph $|E| \geq |V|+1$. To be more explicit:

• $|E| \leq |V|-2$ the graph would not be connected,
• $|E| = |V|-1$ the graph would be a tree (no cycles),
• $|E| = |V|$ the graph would have exactly one cycle,
• $|E| \geq |V| + 1$ is the only possibility.

Then if we remove $e$, we have $|E - \{e\}| \geq |V|$ which still implies the existence of some cycle, which, of course, cannot contain $e$ (it is not necessary, but if you wonder, this connected component is still connected because $e$ was an edge of a cycle).

I hope this helps ;-)

-
add comment

The idea is correct. The problem comes when the two cycles have other edge in common beyond 'e'. How do you manage that case? Do you need to use the hypothesys that the two cycles are distinct?

-
The question states distinct cycles. –  DJ_ Feb 3 at 7:47
Distinct cycles may contain more than one edge in common, so long as they don't contain all their edges in common. –  Steve Kass Feb 3 at 7:49
add comment