Let $G=(V,E) $ be a simple connected graph and $G'$ a spanning tree of $G$.
Show that if $ e $ is an edge of $G $ which is not in $ G'$, then there exists a single cycle of $G$, noted $C_A (e)$, such that $e$ is the only edge of $C_A (e)$ which is not in $G '$.
An idea please.
The easy part is to show there is at least one cycle. If you’ve added the edge $e=uv$, then we can find a cycle using the fact that $G^\prime$ is connected: by definition there is a path from $u$ to $v$ in $G^\prime$, and concatenation $e$ to the end of that path yields a cycle in $G$.
Now, to show this cycle is unique, we will use the fact that $G^\prime$ is acyclic. If there are two cycles in $G$ which contain $e$ and, besides $e$, only use edges in $G^\prime$, then we must have two distinct $uv$ paths in $G^\prime$ (we obtain each such path by deleting $e$ from the corresponding cycle). Let’s traverse these two paths starting at $u$. These paths need not be disjoint, but because they are distinct there must be some vertex, say $x$, at which they diverge. Moreover, these two paths must converge again as they both end at the same vertex $v$. If we let $y$ denote the first vertex after $x$ (when traveling from $u$ to $v$) at which the first path intersects the second path, then we have found two internally disjoint $xy$-paths in $G^\prime$. But two internally disjoint paths together form a cycle, and therefore our assumption that there are two cycles in $G$ containing $e$ and edges of $G^\prime$ leads to a contradiction of the fact that $G^\prime$ is acyclic.