I received a review of one of my papers in which the reviewer made an objection:
"…from the equations e(G) = v(G) you derive that there is a unique simple cycle of G. This is false for non-simple graphs (with loops)."
Here e(G) and v(G) are the number of edges and vertices of the graph, respectively. G is assumed to be connected.
I think the definition of a simple cycle is a path that begins and ends at the same vertex and does not repeat any vertices or edges (and uniqueness is up to cyclic permutation, i.e., the starting point doesn't matter).
I can't think of any counterexample even when I allow multiple edges between vertices, or loops (an edge from a vertex to itself). In fact, I feel like this should be easy to prove. Am I missing something?
Best Answer
Note that we cannot have a simple graph where $e (G)=v (G) $ is one or two. However it is possible to have non-simple graphs which are connected and satisfy $e (G)=v (G) $ without being simple cycles.
Consider a tree with four vertices and three edges. Now add one more edge that either duplicates an existing edge or puts a loop (self-edge) on a leaf vertex.
The result remains connected but is no longer a simple graph, and in particular is neither a simple cycle nor contains a simple cycle except a loop or double-edge between two vertices.
If these are allowed (and the OP has not spoken up to say not so), then we can prove the uniqueness of the simple cycle contained in the connected (undirected) graph $G$.
If $G$ did not contain a cycle, even of the loop or double-edge variety, yet was connected, then it would be tree and $e(G)$ would be $v(G)-1$ (a proof of this by induction is easy and has been discussed previously at Math.SE). On the other hand if $G$ were a connected simple graph with $e(G)=v(G)$, then $G$ itself would be a single cycle of length $e(G)=v(G)$.
Finally if $G$ is connected with $e(G)=v(G)$, then it differs from a spanning tree $T$ contained in $G$ by a single edge. So if $G$ is not itself a cycle, then the extra edge in $G$ but not in $T$ must be a loop (self-edge) or a duplicate (parallel) of an edge in $T$. As any cycle in $G$ must use the edge which doesn't belong to $T$, we see in either of those cases that the "simple cycle" of $G$ is unique, a loop or a pair of parallel edges.