Cycle Graph Properties ($C_n$)

Understanding Cycle Graphs ($C_n$)

In graph theory, a Cycle Graph (denoted as $C_n$) is a graph that consists of a single cycle through all its vertices. It looks like a closed loop, polygon, or ring. The number of vertices ($n$) must be at least 3.

Key Properties

1. Vertices and Edges

For any cycle graph $C_n$:

• Vertices ($V$): $n$
• Edges ($E$): $n$ (Every vertex has a degree of exactly 2)

2. Chromatic Number ($\chi$)

The chromatic number is the minimum number of colors needed to color the vertices so that no two adjacent vertices share the same color.
- If $n$ is even: $\chi(C_n) = 2$ (It is Bipartite)
- If $n$ is odd: $\chi(C_n) = 3$ (It requires a 3rd color for the final connection)

3. Independence Number ($\alpha$)

The size of the largest set of vertices where no two vertices are connected.
- Formula: $\alpha(C_n) = \lfloor n / 2 \rfloor$

4. Bipartite Property

A graph is bipartite if its vertices can be divided into two disjoint sets where every edge connects a vertex in one set to one in the other.
- Only Even Cycles are bipartite.
- Odd Cycles are not bipartite (this is a fundamental theorem: a graph is bipartite iff it contains no odd cycles).

Real World Examples

Ring Topologies: In computer networks, a ring topology is a Cycle Graph. It is simple to build but if one link is cut, the signal must travel the long way around ($n-1$ steps, which is the path length, though diameter is shorter).

Chemistry: Cycloalkanes (like Cyclohexane $C_6H_{12}$) are chemical representations of cycle graphs.