patternMinor
Simple cycles of length two in an undirected graph
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!).
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$.
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.