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}

$A B C D A$ and $B D A B$ are two of the cycles in this graph. $A B A$ is not a cycle, however, since it uses the edge connecting $A$ and $B$ twice. $A B C D$ 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
Canonical name	Cycle
Date of creation	2013-03-22 12:17:21
Last modified on	2013-03-22 12:17:21
Owner	mps (409)
Last modified by	mps (409)
Numerical id	8
Author	mps (409)
Entry type	Definition
Classification	msc 05C38
Related topic	AcyclicGraph
Related topic	SimplePath
Related topic	VeblensTheorem
Related topic	MantelsTheorem
Related topic	Graph