Editing Cycle graph

{{Short description|Graph with nodes connected in a closed chain}}
{{About|connected, 2-regular graphs||Cyclic graph}}
{{infobox graph
 | name = Cycle graph
 | image = [[Image: Circle graph C5.svg|180px]]
 | image_caption = The cycle graph {{math|''C''{{sub|5}}}}
 | automorphisms    = {{math|2{{mvar|n}}}} ({{mvar|D<sub>n</sub>}})
 | chromatic_number = 3 if {{mvar|n}} is odd<br/>2 otherwise
 | chromatic_index = 3 if {{mvar|n}} is odd<br/>2 otherwise
 | girth = {{mvar|n}}
 | spectrum = {{nowrap|<math>\left\{ 2\cos\left(\frac{2k\pi}{n}\right); k=1,\cdots,n \right\}</math><ref>[http://www.win.tue.nl/~aeb/2WF02/easyspectra.pdf Some simple graph spectra]. win.tue.nl</ref>}}
 | notation = {{mvar|C{{sub|n}}}}
 | properties = [[Regular graph|2-regular]]<br>[[Vertex-transitive graph|Vertex-transitive]]<br>[[Edge-transitive graph|Edge-transitive]]<br>[[Unit distance graph|Unit distance]]<br>[[Hamiltonian graph|Hamiltonian]]<br>[[Eulerian graph|Eulerian]]
}}

In [[graph theory]], a '''cycle graph''' or '''circular graph''' is a [[Graph (discrete mathematics)|graph]] that consists of a single [[Cycle (graph theory)|cycle]], or in other words, some number of [[Vertex (graph theory)|vertices]] (at least 3, if the graph is [[Simple graph|simple]]) connected in a closed chain. The cycle graph with {{mvar|n}} vertices is called {{mvar|C{{sub|n}}}}.<ref>{{harvtxt|Diestel|2017}} p. 8, §1.3</ref> The number of vertices in {{mvar|C{{sub|n}}}} equals the number of [[Edge (graph theory)|edge]]s, and every vertex has [[degree (graph theory)|degree]] 2; that is, every vertex has exactly two edges incident with it.

If <math>n = 1</math>, it is an isolated [[Loop (graph theory)|loop]].

==Terminology==
There are many [[synonym]]s 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 [[directed acyclic graph|acyclic]]. Among graph theorists, '''cycle''', '''polygon''', or '''''n''-gon''' are also often used. The term '''''n''-cycle''' is sometimes used in other settings.<ref>{{cite journal |title=Problem 11707 |journal=Amer. Math. Monthly |volume=120 |issue=5 |pages = 469–476|date=May 2013 |doi=10.4169/amer.math.monthly.120.05.469|jstor=10.4169/amer.math.monthly.120.05.469 |s2cid=41161918 }}</ref> 

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'''.

==Properties==
A cycle graph is:
* [[k-edge colorable|2-edge colorable]], if and only if it has an even number of vertices
* [[regular graph|2-regular]]
* [[Bipartite graph|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 ([[Dénes Kőnig|Kőnig]], 1936).
* [[Connected graph|Connected]]
* [[Eulerian graph|Eulerian]]
* [[Hamiltonian graph|Hamiltonian]]
* A [[unit distance graph]]

In addition: 
*As cycle graphs can be [[graph drawing|drawn]] as [[regular polygon]]s, the [[automorphism group|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 graph]]s, the cycle graphs form the skeletons of the [[dihedron|dihedra]]. Their duals are the [[dipole graph]]s, which form the skeletons of the [[hosohedron|hosohedra]].

==Directed cycle graph==
[[Image:DC8.png|frame|right|A directed cycle graph of length 8]]
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&nbsp;1 and uniform out-degree&nbsp;1.

Directed cycle graphs are [[Cayley graph]]s for [[cyclic group]]s (see e.g. Trevisan).

==See also==
{{commons category|Cycle graphs}}
* [[Complete bipartite graph]]
* [[Complete graph]]
*[[Circulant graph]]
*[[Cycle graph (algebra)]]
* [[Null graph]]
* [[Path graph]]

==References==
{{reflist}}

== Sources ==
* {{Cite book|last=Diestel|first=Reinhard|author-link = Reinhard Diestel|title=Graph Theory|publisher=[[Springer Science+Business Media | Springer]]|year=2017|isbn=978-3-662-53621-6|edition=5}}

==External links==
*{{MathWorld |urlname=CycleGraph |title=Cycle Graph}} (discussion of both 2-regular cycle graphs and the group-theoretic concept of [[cycle diagram]]s)
*[[Luca Trevisan]], [http://in-theory.blogspot.com/2006/12/characters-and-expansion.html Characters and Expansion].

[[Category:Parametric families of graphs]]
[[Category:Regular graphs]]