# cycle

A cycle in a graph, digraph, or multigraph, is a simple path from a vertex to itself (i.e., a path where the first vertex is the same as the last vertex and no edge is repeated).

For example, consider this graph:

 $\xymatrix{A\ar@{-}[r]\ar@{-}[d]&B\ar@{-}[dl]\ar@{-}[d]\\ D\ar@{-}[r]&C}$

$ABCDA$ and $BDAB$ are two of the cycles in this graph. $ABA$ is not a cycle, however, since it uses the edge connecting $A$ and $B$ twice. $ABCD$ is not a cycle because it begins on $A$ but ends on $D$.

A cycle of length $n$ is sometimes denoted $C_{n}$ and may be referred to as a polygon of $n$ sides: that is, $C_{3}$ is a triangle, $C_{4}$ is a quadrilateral, $C_{5}$ is a pentagon, etc.

An even cycle is one of even length; similarly, an odd cycle is one of odd length.

Title cycle Cycle 2013-03-22 12:17:21 2013-03-22 12:17:21 mps (409) mps (409) 8 mps (409) Definition msc 05C38 AcyclicGraph SimplePath VeblensTheorem MantelsTheorem Graph