HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Simple cycles of length two in an undirected graph

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
simplegraphlengthtwoundirectedcycles

Problem

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!).

Solution

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$.

Context

StackExchange Computer Science Q#115158, answer score: 5

Revisions (0)

No revisions yet.