Cycles and Connectivity

Definition

A cycle in a graph is a path that starts and ends at the same vertex, with no repeated edges and no repeated vertices except the first and last vertex.

A graph is connected if there is a path between every pair of vertices in the graph. In a connected graph, all vertices belong to a single connected component. If a graph is not connected, it can be split into two or more disconnected components.

Main Content

1. Cycles in Graphs

A cycle is a closed walk where the starting and ending vertices are the same, and no edge is used more than once; in a simple cycle, no vertex is repeated except the first and last.
Cycles reveal important structural information: they show that a graph is not a tree, indicate redundancy in connections, and help detect loops in networks.

A cycle can be visualized as a round trip. For example, if vertices are connected as $A \to B \to C \to A$ , then these three vertices form a cycle of length 3.

Example: If a graph has edges $(1,2), (2,3), (3,1)$ , then the sequence $1 \to 2 \to 3 \to 1$ is a cycle.

Types of cycles:

Simple cycle

No repeated vertices except the first and last.

Directed cycle

In a directed graph, all edges follow the same direction around the loop.

Undirected cycle

A closed path in an undirected graph.

Self-loop

An edge from a vertex to itself; this is a cycle of length 1 in many contexts.

ASCII view of a cycle:

A ---- B
|      |
|      |
D ---- C

This square graph contains a cycle: $A \to B \to C \to D \to A$ .

2. Connectivity in Graphs

Connectivity measures whether vertices in a graph are reachable from one another through paths.
A graph with strong connectivity has one large component, while a disconnected graph has isolated groups of vertices that cannot reach each other.

For an undirected graph, connectivity means there is at least one path between every pair of vertices. Such a graph is called connected. If not, the graph is divided into connected components, each of which is itself connected.

In directed graphs, connectivity is studied in two main ways:

Strong connectivity

For every pair of vertices $u$ and $v$ , there is a directed path from $u$ to $v$ and from $v$ to $u$ .

Weak connectivity

If edge directions are ignored and the underlying undirected graph is connected, then the directed graph is weakly connected.

Example:

A road map where all cities can be reached from one another represents a connected graph.
A social network with separated friend groups may be disconnected.

ASCII view of a disconnected graph:

A --- B      C --- D

There is no path between the pair $\{A,B\}$ and $\{C,D\}$ , so the graph is disconnected.

3. Relationship Between Cycles and Connectivity

A graph can be connected without containing any cycle; such a graph is a tree.
If a connected graph has exactly one more edge than a tree on the same number of vertices, it often contains a cycle; generally, extra edges beyond a spanning tree create cycles.

This relationship is very important:

Trees

are connected and acyclic.

Cycles

indicate the presence of alternative routes.
A graph may be connected even if it has many cycles.
A graph may have cycles in one component while another component remains disconnected.

A key result in graph theory is:

A connected graph with $n$ vertices and $n-1$ edges and no cycle is a tree.
If a connected graph has more than $n-1$ edges, it must contain at least one cycle.

Example: A triangle graph with vertices $1,2,3$ is connected and contains a cycle. A straight chain $1-2-3$ is connected but has no cycle.

Diagram for understanding the difference:

Tree (connected, no cycle):      Cycle graph:
1 --- 2 --- 3                   1 --- 2
                                |     |
                                4 --- 3

Working / Process

Start by listing the vertices and edges of the graph, then determine whether the graph is directed or undirected, because the idea of connectivity differs in each case.
Check for paths between vertices by using traversal methods such as Depth First Search (DFS) or Breadth First Search (BFS); if all vertices are visited from one starting vertex, the graph is connected.
To detect cycles, follow edges carefully during traversal; in undirected graphs, revisiting an already visited vertex other than the parent may indicate a cycle, while in directed graphs, a back edge during DFS often confirms a cycle.

Advantages / Applications

Helps in analyzing computer networks, where connectivity shows whether communication is possible and cycles provide backup paths if one link fails.
Used in transportation and road systems to identify reachable locations, circular routes, and alternative travel paths.
Important in algorithm design, such as detecting deadlocks in operating systems, finding spanning trees, and checking whether a graph is a tree or has redundancy.

Summary

Cycles are closed paths in a graph, while connectivity tells whether all vertices are reachable from one another.
Connected graphs form a single component; disconnected graphs have multiple components.
Cycles show redundancy and alternate routes, while acyclic connected graphs are trees.
Important terms to remember: cycle, connected graph, disconnected graph, connected component, strong connectivity, weak connectivity, tree, path.