As the title says, I am trying to show that if $G$ is a finite simple graph with no even cycles, then each edge is in at most one cycle.
I'm trying to do this by contradiction: let $e$ be an edge of $G$, and for contradiction suppose that $e$ was in two distinct cycles $C_1$ and $C_2$ of $G$. By assumption, $C_1$ and $C_2$ must have odd length. Now I would like to somehow patch $C_1$ and $C_2$ together to obtain a cycle of even length, but I'm not sure how to do so. If $C_1$ and $C_2$ only overlap in $e$, or perhaps in a single path containing $e$, then this can be done, but I can't see how to make this patching work when $C_1$ and $C_2$ overlap in disjoint paths.
Any help is appreciated!
Best Answer
Here is the rough idea:
Suppose $C_1$ and $C_2$ overlap in at least two disjoint paths. If we follow $C_1$ along the end of one path to the beginning of the next path, and then follows $C_2$ back to the end of the first path, we obtain a cycle $C_3$. Since this cycle must have odd length, the parity of the two parts must be different. This means I can change the parity of the length of $C_1$ by following the $C_2$ part of $C_3$ instead of the $C_1$ part. This is also a contradiction, as $C_1$ has odd length.
Explicitly, let $a$ be the last vertex of one path contained in both $C_1$ and $C_2$, and let $b$ be the first vertex of the next path contained in both $C_1$ and $C_2$. Let $C_3$ be the cycle obtained by following $C_1$ from $a$ to $b$, and then following $C_2$ back to $a$. Since $C_3$ has odd length, the parity of the length along $C_1$ from $a$ to $b$ must be different from the parity of the length of $C_2$ from $a$ to $b$. It is this difference in parity that allows us to modify $C_1$. That is, let $C_1'$ be the cycle that agrees with $C_1$ except for the path from $a$ to $b$, where it agrees with $C_2$. Then $C_1'$ will have even length.