PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
cycle (Definition)

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.




Anyone with an account can edit this entry. Please help improve it!

"cycle" is owned by mps. [ full author list (2) | owner history (1) ]
(view preamble | get metadata)

View style:

See Also: acyclic graph, simple path, Veblen's theorem, Mantel's theorem, graph

Log in to rate this entry.
(view current ratings)

Cross-references: odd, even, pentagon, quadrilateral, triangle, sides, polygon, length, edge, path, vertex, simple path, multigraph, digraph, graph
There are 9 references to this entry.

This is version 5 of cycle, born on 2002-02-04, modified 2004-03-30.
Object id is 1805, canonical name is Cycle.
Accessed 5445 times total.

Classification:
AMS MSC05C38 (Combinatorics :: Graph theory :: Paths and cycles)

Pending Errata and Addenda
None.
[ View all 4 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)