6
$\begingroup$

Pedagogical question.

Background

A cycle in a graph can be defined as a sequence of vertices $v_1,\dots,v_n$ with $v_1=v_n$ such that, for each $i \in \{1,\dots,n-1\}$, the graph has an edge $(v_i,v_{i+1})$. (One can define it differently.)

The point

Every definition of simple cycle I have seen is: a cycle with no repeated vertices, except the first and last.

But this definition implies that even in undirected graphs, we can have simple cycles of length two, e.g. $u \to v \to u$. However, we probably do not want to consider this a simple cycle because it re-uses the edge $(u,v)$ and this would break several algorithms and proofs.

Of course for cycles of length $3$ or more, requiring no repeated vertices implies there are no repeated edges.

The question

Which of the following is right? Justify your answer.

(1) The standard definitions are incorrect, they ought to explicitly exclude simple cycles of length 2 in undirected graphs.

(2) The standard definitions are correct, the cycle of length 2 is simple.

(3) This question is wrong in claiming this is the standard definition of simple cycle. There are other better definitions that are standard (references please!).

$\endgroup$
  • 1
    $\begingroup$ A cycle is a non-empty trail in which the first and last vertex are repeated. In your example, $uvu$ is not a cycle because in a trail all edges are distinct. There's no need to explicitly forbid length-2 cycles, the definition of a trail takes care of this. $\endgroup$ – Juho Sep 27 '19 at 13:55
  • $\begingroup$ @Juho textbook reference? Any used commonly in CS courses? $\endgroup$ – usul Sep 27 '19 at 19:35
  • $\begingroup$ Also, I'm not excited about your definition because I prefer to distinguish "simple cycle" (which you call a cycle) from a "cycle" (which may contain repeated edges, not sure what you would call it). $\endgroup$ – usul Sep 27 '19 at 19:43
  • $\begingroup$ @usul 'Also, I'm not excited about your definition because I prefer to distinguish "simple cycle" (which you call a cycle) from a "cycle" (which may contain repeated edges, not sure what you would call it).' I believe that what you refer to as a cycle (not simple), would be called a closed walk. $\endgroup$ – integrator Sep 28 '19 at 9:24
  • $\begingroup$ I agree with @Juho in that the definition he gave is the most common, although there are authors who define it to be a closed path, e.g. Wilson's 1996 book. $\endgroup$ – flow2k Jun 20 at 7:08
3
$\begingroup$

I'll go with (3)

From Bondy and Murty's Graph Theory with Applications (http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_Bondy_Murty.pdf), sections 1.6 "Paths and Connections" and 1.7 "Cycles":

A walk is a finite non-null sequence of alternating vertices and edges (repetition of both allowed).

If the edges of a walk are distinct then it is also a trail. If in addition the vertices are distinct then the trail is a path.

A walk is closed if it has positive length (defined as its number of edges) and its origin and terminus are the same (vertex). A closed trail whose origin and internal vertices are distinct is a cycle.

SUMMARY: So in this system of definitions, a cycle cannot repeat edges or vertices except the origin/terminus, which excludes walks of length two.

However, it is true that there are other contradictory definitions in the literature which is why it is best to always restate the definitions in say a paper or course.

PS: For the sake of completion, I believe that in this system of definitions (although I did look for it in this particular reference), a circuit is a closed trail (repetition of vertices allowed, but not of edges).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, I'm accepting this answer. Although, I don't think CS students at least in the US are often taught these versions of the definitions. $\endgroup$ – usul Sep 30 '19 at 23:24
5
$\begingroup$

It turns out that the very popular textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, sneakily avoids this issue by giving a different definition of cycle in undirected vs directed graphs.

In Section B.4, it defines cycle and simple cycle as I do (they also require at least one edge), in directed graphs. In an undirected graph, they define cycle the same way except they require that all of the edges in the cycle be distinct; and they say the cycle is simple if in addition the vertices are distinct, other than $v_1=v_k$.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

Arguably two of the most definite textbooks on graph theory are Bundy & Murty (BM) (roughly 15000 citations at the time of writing) and Diestel (at least hundreds of citations).

In BM (Section 1.6), the definition of a cycle is obtained via walks and trails, i.e., a cycle is a non-empty trail in which the first and last vertex are repeated. In your example, $uvu$ is not a cycle because in a trail all edges are distinct. So in particular, there's no need to explicitly forbid length-2 cycles as the definition of a trail takes care of this.

In Diestel (Section 1.3), the author begins by defining a path $P=(V,E)$ with $V=\{x_0,x_1,\ldots,x_k\}$ and $E=\{x_0x_1,x_1,x_2,\ldots,x_{k-1}x_k\}$. Then, if $P=x_0,\ldots,x_{k-1}$ is a path and $k \geq 3$, the graph $C := P + x_{k-1}x_0$ is a cycle.

In addition, the current Wikipedia entry on a cycle refers to Bender & Williamson which seems to use the same definition as BM.

In summary, both definitions should capture precisely the set of objects.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, I've accepted the other answer as it was earlier and has high overlap, but this is helpful. $\endgroup$ – usul Sep 30 '19 at 23:25

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.