4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ A loop is a simple cycle: it repeats no edge, and the only repeated vertex is the one at which it begins and ends. $\endgroup$ – Brian M. Scott Aug 18 '16 at 19:17
  • 2
    $\begingroup$ @BrianM.Scott: I think "loops" here has the sense of a self-edge, which is why the number of edges and vertices can be decoupled from existence of "a unique simple cycle". $\endgroup$ – hardmath Aug 18 '16 at 19:24
  • $\begingroup$ I second @hardmath's comment - a simple graph cannot have an edge from a vertex to itself, nor multiple edges between a single pair of vertices. But a non-simple graph could consist of two vertices, $a$ and $b$, and edges from $a$ to $a$, and from $b$ to $b$. Here $e(G) = v(G)$ but there is not a unique simple cycle in $G$. $\endgroup$ – Titus Aug 18 '16 at 19:33
  • $\begingroup$ @Titus "$G$ is assumed to be connected." $\endgroup$ – bof Aug 18 '16 at 19:34
  • $\begingroup$ @Titus: Your example illustrates the reviewer’s point. I don’t see the point of hardmath’s comment, since we’re apparently talking about exactly the same thing: an edge from a vertex $v$ to $v$. $\endgroup$ – Brian M. Scott Aug 18 '16 at 19:38
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The Wikipedia article on cycles defines a simple cycle as "a closed walk with no repetitions of vertices and edges allowed, other than the repetition of the starting and ending vertex." By that definition, a graph containing one vertex $v$ and one edge joining $v$ to $v$ is a simple cycle, and so is a graph containing two vertices $u,v$ and two edges joining $u$ to $v$. Of course neither of those simple cycles is a simple graph. $\endgroup$ – bof Aug 18 '16 at 22:53
  • $\begingroup$ The use of terms cycle and simple cycle vary with authors. I've edited my last statement to exclude the cases noted in my opening paragraph. $\endgroup$ – hardmath Aug 18 '16 at 23:28
  • 1
    $\begingroup$ I expect that this was this confusion: the reviewer was assuming that a loop or multi-edge is not a cycle (i.e. a cycle has length at least 3), but I was assuming that they are. I'll be sure to clarify this in my paper. I'll accept this answer. $\endgroup$ – paragon Aug 20 '16 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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