Cycle graph

In the mathematical field of graph theory a cycle graph or circle graph is a graph that consists of a cycle. The circle graph with <math>n<math> vertices is called <math>C_n<math>.

A directed cycle graph or a dicycle graph is a diconnected cycle graph, that is all directed edges in the cycle point in the same direction.

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

Properties

• A circle graph is
• connected
• 2-regular.
• Eulerian.
• Hamiltonian.
• symmetric.
• 2-vertex colorable and 2-edge colorable if it has an even number vertices.
• 3-vertex colorable and 3-edge colorable if it has an odd number of vertices.
• Any connected graph with a subgraph that is a cycle is not a tree.
• Cycles with an even number of vertices are bipartite, cycles with an odd number are not.
• Cycles with an even number of vertices can be decomposed into a minimum of 2 independent sets (i.e. <math>\alpha(n)=2<math>), whereas cycles with an odd number of vertices can be decomposed into a minimum of 3 independent sets (i.e. <math>\alpha(n)=3<math>).

See also

• Cycle graph (group) – using cycle graphs to illustrate the structure of small finite groups

References

• Eric W. Weisstein, Cycle Graph at MathWorld.