Cycle graph

<h2 id="terminology">Terminology</h2>
<p>There are many <a href="/facts/Synonym/a3BgMcdu">synonyms</a> 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 <a href="/facts/Directed_acyclic_graph/k6zq1os9">acyclic</a>. Among graph theorists, cycle, polygon, or <i>n</i>-gon are also often used. The term <i>n</i>-cycle is sometimes used in other settings.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> 
</p><p>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.
</p>
<h2 id="properties">Properties</h2>
<p>A cycle graph is:
</p>
<ul><li><a href="/facts/K-edge_colorable/AcdpUxCv">2-edge colorable</a>, if and only if it has an even number of vertices</li>
<li><a href="/facts/Regular_graph/j9dSoLE6">2-regular</a></li>
<li><a href="/facts/Bipartite_graph/xWcXV9MB">2-vertex colorable</a>, if and only if it has an even number of vertices. More generally, a graph is bipartite <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> it has no odd cycles (<a href="/facts/D%25C3%25A9nes_K%25C5%2591nig/wNMBmsYK">Kőnig</a>, 1936).</li>
<li><a href="/facts/Connected_graph/FSNjsYhz">Connected</a></li>
<li><a href="/facts/Eulerian_graph/4l2G67c7">Eulerian</a></li>
<li><a href="/facts/Hamiltonian_graph/MHjY2xoY">Hamiltonian</a></li>
<li>A <a href="/facts/Unit_distance_graph/8y4Ctq53">unit distance graph</a></li></ul>
<p>In addition: 
</p>
<ul><li>As cycle graphs can be <a href="/facts/Graph_drawing/uhh73BVo">drawn</a> as <a href="/facts/Regular_polygon/ws89Nhpt">regular polygons</a>, the <a href="/facts/Automorphism_group/65vImKwe">symmetries</a> of an <i>n</i>-cycle are the same as those of a regular polygon with <i>n</i> sides, the <a href="/facts/Dihedral_group/1PUlRh4M">dihedral group</a> of order 2<i>n</i>. In particular, there exist symmetries taking any vertex to any other vertex, and any edge to any other edge, so the <i>n</i>-cycle is a <a href="/facts/Symmetric_graph/vPVWrnjb">symmetric graph</a>.</li></ul>
<p>Similarly to the <a href="/facts/Platonic_graph/Py7GVQGk">Platonic graphs</a>, the cycle graphs form the skeletons of the <a href="/facts/Dihedron/YkNgovlv">dihedra</a>. Their duals are the <a href="/facts/Dipole_graph/9ceBgwJY">dipole graphs</a>, which form the skeletons of the <a href="/facts/Hosohedron/t2dyV0bW">hosohedra</a>.
</p>
<h2 id="directed-cycle-graph">Directed cycle graph</h2>

<p>A directed cycle graph is a directed version of a cycle graph, with all the edges being oriented in the same direction.
</p><p>In a <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a>, a set of edges which contains at least one edge (or <i>arc</i>) from each directed cycle is called a <a href="/facts/Feedback_arc_set/p69AScPL">feedback arc set</a>. Similarly, a set of vertices containing at least one vertex from each directed cycle is called a <a href="/facts/Feedback_vertex_set/Kzr6n97M">feedback vertex set</a>.
</p><p>A directed cycle graph has uniform in-degree 1 and uniform out-degree 1.
</p><p>Directed cycle graphs are <a href="/facts/Cayley_graph/QxoxNnys">Cayley graphs</a> for <a href="/facts/Cyclic_group/JL5zfFuL">cyclic groups</a> (see e.g. Trevisan).
</p>
<h2 id="see-also">See also</h2>

Wikimedia Commons has media related to Cycle graphs.

<ul><li><a href="/facts/Complete_bipartite_graph/C1RYIdpX">Complete bipartite graph</a></li>
<li><a href="/facts/Complete_graph/AYD6hUqI">Complete graph</a></li>
<li><a href="/facts/Circulant_graph/b51YF380">Circulant graph</a></li>
<li><a href="/facts/Cycle_graph_(algebra)/Rca39VN9">Cycle graph (algebra)</a></li>
<li><a href="/facts/Null_graph/Ro1YV0g6">Null graph</a></li>
<li><a href="/facts/Path_graph/4Y2f35eM">Path graph</a></li></ul>

<h2 id="sources">Sources</h2>
<ul><li><a href="/facts/Reinhard_Diestel/Fzv2bX8x">Diestel, Reinhard</a> (2017). <i>Graph Theory</i> (5 ed.). <a href="/facts/Springer_Science%252BBusiness_Media/nAesf6nT"> Springer</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-662-53621-6.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/CycleGraph.html">"Cycle Graph"</a>. <i><a href="/facts/MathWorld/yc1jodbq">MathWorld</a></i>. (discussion of both 2-regular cycle graphs and the group-theoretic concept of <a href="/facts/Cycle_diagram/Rca39VN9">cycle diagrams</a>)</li>
<li><a href="/facts/Luca_Trevisan/oFlHonQ0">Luca Trevisan</a>, <a href="http://in-theory.blogspot.com/2006/12/characters-and-expansion.html">Characters and Expansion</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Diestel (2017) p. 8, §1.3 - Diestel, Reinhard (2017). Graph Theory (5 ed.).  Springer. ISBN 978-3-662-53621-6. <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>"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. S2CID 41161918. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Cycle graph open-in-new

Cycle graph