(Redirected from
Odd cycle)
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 n vertices is called Cn.
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. α(n) = 2), whereas cycles with an odd number of vertices can be decomposed into a minimum of 3 independent sets (i.e. α(n) = 3).
See also
References
