In graph theory, what is the difference between a cycle and a simple cycle? My impression is that a simple cycle is the same as a cycle except that you cannot repeat vertices. Is this correct?
$\endgroup$1 Answer
$\begingroup$This is correct.
Write $v \rightarrow w$ to mean that there is an edge from $v$ to $w$. A cycle is any finite sequence of vertices $v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n$ such that $v_i = v_j$ for some $i \neq j$. A simple cycle has the additional requirement that if $v_i = v_j$ and $i \neq j$, then $i, j \in \{1, n\}$.
$\endgroup$
