# Cycle graph

In graph theory, a **cycle graph** or **circular graph** is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with *n* vertices is called *C _{n}*. The number of vertices in

*C*equals the number of edges, and every vertex has degree 2; that is, every vertex has exactly two edges incident with it.

_{n}Cycle graph | |
---|---|

A cycle graph of length 6 | |

Vertices | n |

Edges | n |

Girth | n |

Automorphisms | 2n (D)_{n} |

Chromatic number | 3 if n is odd2 otherwise |

Chromatic index | 3 if n is odd2 otherwise |

Spectrum | {2 cos(2kπ/n); k = 1, ..., n} ^{[1]} |

Properties | 2-regular Vertex-transitive Edge-transitive Unit distance Hamiltonian Eulerian |

Notation | |

Table of graphs and parameters |

## TerminologyEdit

There are many synonyms for "cycle graph". These include **simple cycle graph** and **cyclic graph**, although the latter term is less often used, because it can also refer to graphs which are merely not acyclic. Among graph theorists, **cycle**, **polygon**, or ** n-gon** are also often used. The term

**is sometimes used in other settings.**

*n*-cycle^{[2]}

A cycle with an even number of vertices is called an **even cycle**; a cycle with an odd number of vertices is called an **odd cycle**.

## PropertiesEdit

A cycle graph is:

- 2-edge colorable, if and only if it has an even number of vertices
- 2-regular
- 2-vertex colorable, if and only if it has an even number of vertices. More generally, a graph is bipartite if and only if it has no odd cycles (Kőnig, 1936).
- Connected
- Eulerian
- Hamiltonian
- A unit distance graph

In addition:

- As cycle graphs can be drawn as regular polygons, the symmetries of an
*n*-cycle are the same as those of a regular polygon with*n*sides, the dihedral group of order 2*n*. In particular, there exist symmetries taking any vertex to any other vertex, and any edge to any other edge, so the*n*-cycle is a symmetric graph.

Similarly to the Platonic graphs, the cycle graphs form the skeletons of the dihedra. Their duals are the dipole graphs, which form the skeletons of the hosohedra.

## Directed cycle graphEdit

A **directed cycle graph** is a directed version of a cycle graph, with all the edges being oriented in the same direction.

In a directed graph, a set of edges which contains at least one edge (or *arc*) from each directed cycle is called a feedback arc set. Similarly, a set of vertices containing at least one vertex from each directed cycle is called a feedback vertex set.

A directed cycle graph has uniform in-degree 1 and uniform out-degree 1.

Directed cycle graphs are Cayley graphs for cyclic groups (see e.g. Trevisan).

## See alsoEdit

Wikimedia Commons has media related to .Cycle graphs |

## ReferencesEdit

**^**Some simple graph spectra. win.tue.nl**^**"Problem 11707".*Amer. Math. Monthly*.**120**(5): 469–476. May 2013. doi:10.4169/amer.math.monthly.120.05.469. JSTOR 10.4169/amer.math.monthly.120.05.469.

## External linksEdit

- Weisstein, Eric W. "Cycle Graph".
*MathWorld*. (discussion of both 2-regular cycle graphs and the group-theoretic concept of cycle diagrams) - Luca Trevisan, Characters and Expansion.