Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I figured I would note that the cycle space is a vector space. In particular, it is a subspace of edge space. The vectors are edge sets, with the finite field $\{0, 1\}$ and addition as the symmetric difference. In cycle space, the edge sets all form cycles, save for the empty set. Since cycle is closed under addition, we have that the symmetric difference of two cycles yields a cycle in the graph. –  ml0105 Mar 18 at 4:16

2 Answers 2

up vote 1 down vote accepted

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 ;-)

share|improve this answer

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?

share|improve this answer
    
The question states distinct cycles. –  DJ_ Feb 3 '13 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 '13 at 7:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.