# Cycle (graph theory) Information

*https://en.wikipedia.org/wiki/Cycle_(graph_theory)*

In
graph theory, a **cycle** in a
graph is a non-empty
trail in which only the first and last
vertices are equal. A **directed cycle** in a
directed graph is a non-empty
directed trail in which only the first and last vertices are equal.

A graph without cycles is called an *acyclic graph*. A directed graph without directed cycles is called a *
directed acyclic graph*. A
connected graph without cycles is called a *
tree*.

## Definitions

### Circuit and cycle

- A
**circuit**is a non-empty trail in which the first and last vertices are equal (*closed trail*).^{ [1]}

- Let
*G*= (*V*,*E*,*ϕ*) be a graph. A circuit is a non-empty trail (*e*_{1},*e*_{2}, …,*e*_{n}) with a vertex sequence (*v*_{1},*v*_{2}, …,*v*_{n},*v*_{1}).

- A
**cycle**or**simple circuit**is a circuit in which only the first and last vertices are equal.^{ [1]}

### Directed circuit and directed cycle

- A
**directed circuit**is a non-empty directed trail in which the first and last vertices are equal (*closed directed trail*).^{ [1]}

- Let
*G*= (*V*,*E*,*ϕ*) be a directed graph. A directed circuit is a non-empty directed trail (*e*_{1},*e*_{2}, …,*e*_{n}) with a vertex sequence (*v*_{1},*v*_{2}, …,*v*_{n},*v*_{1}).

- A
**directed cycle**or**simple directed circuit**is a directed circuit in which only the first and last vertices are equal.^{ [1]}

## Chordless cycle

A chordless cycle in a graph, also called a hole or an induced cycle, is a cycle such that no two vertices of the cycle are connected by an edge that does not itself belong to the cycle. An antihole is the complement of a graph hole. Chordless cycles may be used to characterize perfect graphs: by the strong perfect graph theorem, a graph is perfect if and only if none of its holes or antiholes have an odd number of vertices that is greater than three. A chordal graph, a special type of perfect graph, has no holes of any size greater than three.

The girth of a graph is the length of its shortest cycle; this cycle is necessarily chordless. Cages are defined as the smallest regular graphs with given combinations of degree and girth.

A peripheral cycle is a cycle in a graph with the property that every two edges not on the cycle can be connected by a path whose interior vertices avoid the cycle. In a graph that is not formed by adding one edge to a cycle, a peripheral cycle must be an induced cycle.

## Cycle space

The term *cycle* may also refer to an element of the
cycle space of a graph. There are many cycle spaces, one for each coefficient field or ring. The most common is the *binary cycle space* (usually called simply the *cycle space*), which consists of the edge sets that have even degree at every vertex; it forms a
vector space over the two-element
field. By
Veblen's theorem, every element of the cycle space may be formed as an edge-disjoint union of simple cycles. A
cycle basis of the graph is a set of simple cycles that forms a
basis of the cycle space.^{
[2]}

Using ideas from
algebraic topology, the binary cycle space generalizes to vector spaces or
modules over other
rings such as the integers, rational or real numbers, etc.^{
[3]}

## Cycle detection

The existence of a cycle in directed and undirected graphs can be determined by whether
depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (it contains a
back edge).^{
[4]} All the back edges which DFS skips over are part of cycles.^{
[5]} In an undirected graph, the edge to the parent of a node should not be counted as a back edge, but finding any other already visited vertex will indicate a back edge. In the case of undirected graphs, only *O*(*n*) time is required to find a cycle in an *n*-vertex graph, since at most *n* − 1 edges can be tree edges.

Many
topological sorting algorithms will detect cycles too, since those are obstacles for topological order to exist. Also, if a directed graph has been divided into
strongly connected components, cycles only exist within the components and not between them, since cycles are strongly connected.^{
[5]}

For directed graphs, distributed message based algorithms can be used. These algorithms rely on the idea that a message sent by a vertex in a cycle will come back to itself. Distributed cycle detection algorithms are useful for processing large-scale graphs using a distributed graph processing system on a computer cluster (or supercomputer).

Applications of cycle detection include the use of
wait-for graphs to detect
deadlocks in concurrent systems.^{
[6]}

## Algorithm

For every vertex v: visited(v) = false, finished(v) = false For every vertex v: DFS(v)

DFS(v): if finished(v) return if visited(v) "Cycle found" and return visited(v) = true for every neighbour w DFS(w) finished(v) = true

Neighbour means for both directed and undirected graphs all vertices connected to *v*, except for the one that called *DFS(v)*. This avoids the algorithm also catching trivial cycles, which is the case in every undirected graph with at least one edge.

## Programming

The following example in the
Programming language
C# shows one implementation of an undirected graph using
Adjacency lists. The undirected graph is declared as
class *UndirectedGraph*. Executing the program uses the *Main*
method, which - if one exists - prints the shortest, non-trivial cycle to the console.^{
[7]}

```
using System;
using System.Collections.Generic;
// Declares the class for the vertices of the graph
class Node
{
public int index;
public string value;
public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Set of neighbour vertices
}
// Declares the class for the undirected graph
class UndirectedGraph
{
public HashSet<Node> nodes = new HashSet<Node>();
// This method connects node1 and node2 with each other
public void ConnectNodes(Node node1, Node node2)
{
node1.adjacentNodes.Add(node2);
node2.adjacentNodes.Add(node1);
}
}
class Program
{
// This method returns the cycle in the form A, B, C, ... as text.
public static string ToString(List<Node> cycle)
{
string text = "";
for (int i = 0; i < cycle.Count; i++) // for-loop, iterating the vertices
{
text += cycle[i].value + ", ";
}
text = text.Substring(0, text.Length - 2);
return text;
}
// Main method executing the program
public static void Main(string[] args)
{
// Declares and initialises 5 vertices
Node node1 = new Node{index = 0, value = "A"};
Node node2 = new Node{index = 1, value = "B"};
Node node3 = new Node{index = 2, value = "C"};
Node node4 = new Node{index = 3, value = "D"};
// Declares and initialises an array holding the vertices
Node[] nodes = {node1, node2, node3, node4};
// Creates an undirected graph
UndirectedGraph undirectedGraph = new UndirectedGraph();
int numberOfNodes = nodes.Length;
for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices
{
undirectedGraph.nodes.Add(nodes[i]); // Adds the vertices to the graph
}
// Connects the vertices of the graph with each other
undirectedGraph.ConnectNodes(node1, node1);
undirectedGraph.ConnectNodes(node1, node2);
undirectedGraph.ConnectNodes(node2, node3);
undirectedGraph.ConnectNodes(node3, node1);
undirectedGraph.ConnectNodes(node3, node4);
undirectedGraph.ConnectNodes(node4, node1);
HashSet<Node> newNodes = new HashSet<Node>(nodes); // Set of new vertices to iterate
HashSet<List<Node>> paths = new HashSet<List<Node>>(); // Set of current paths
for (int i = 0; i < numberOfNodes; i++) // for-loop, iterating all vertices of the graph
{
Node node = nodes[i];
newNodes.Add(node); // Add the vertex to the set of new vertices to iterate
List<Node> path = new List<Node>();
path.Add(node);
paths.Add(path); // Adds a path for each node as a starting vertex
}
HashSet<List<Node>> shortestCycles = new HashSet<List<Node>>(); // Set of shortest cycles
int lengthOfCycles = 0; // Length of shortest cycles
bool cyclesAreFound = false; // Whether or not cycles were found at all
while (!cyclesAreFound && newNodes.Count > 0) // As long as we still had vertices to iterate
{
newNodes.Clear(); // Empties the set of nodes to iterate
HashSet<List<Node>> newPaths = new HashSet<List<Node>>(); // Set of newly found paths
foreach (List<Node> path in paths) // foreach-loop, iterating all current paths
{
Node lastNode = path[path.Count - 1];
newNodes.Add(lastNode); // Adds the final vertex of the path to the list of vertices to iterate
foreach (Node nextNode in lastNode.adjacentNodes) // foreach-loop, iterating all neighbours of the previous node
{
if (path.Count >= 3 && path[0] == nextNode) // If a cycle with length greater or equal 3 was found
{
cyclesAreFound = true;
shortestCycles.Add(path); // Adds the path to the set of cycles
lengthOfCycles = path.Count;
}
if (!path.Contains(nextNode)) // If the path doesn't contain the neighbour
{
newNodes.Add(nextNode); // Adds the neighbour to the set of vertices to iterate
// Creates a new path
List<Node> newPath = new List<Node>();
newPath.AddRange(path); // Adds the current path's vertex to the new path in the correct order
newPath.Add(nextNode); // Adds the neighbour to the new path
newPaths.Add(newPath); // Adds the path to the set of newly found paths
}
}
}
paths = newPaths; // Updates the set of current paths
}
if (shortestCycles.Count > 0) // If cycles were found
{
Console.WriteLine("The graph contains " + shortestCycles.Count + " cycles of length " + lengthOfCycles + "."); // Print to console
foreach (List<Node> cycle in shortestCycles) // foreach-loop, iterating all found cycles
{
Console.WriteLine(ToString(cycle)); // Print to console
}
}
else
{
Console.WriteLine("The graph contains no cycles."); // Print to console
}
Console.ReadLine();
}
}
```

## Covering graphs by cycle

In his 1736 paper on the
Seven Bridges of Königsberg, widely considered to be the birth of graph theory,
Leonhard Euler proved that, for a finite undirected graph to have a closed walk that visits each edge exactly once (making it a closed trail), it is necessary and sufficient that it be connected except for isolated vertices (that is, all edges are contained in one component) and have even degree at each vertex. The corresponding characterization for the existence of a closed walk visiting each edge exactly once in a directed graph is that the graph be
strongly connected and have equal numbers of incoming and outgoing edges at each vertex. In either case, the resulting closed trail is known as an
Eulerian trail. If a finite undirected graph has even degree at each of its vertices, regardless of whether it is connected, then it is possible to find a set of simple cycles that together cover each edge exactly once: this is
Veblen's theorem.^{
[8]} When a connected graph does not meet the conditions of Euler's theorem, a closed walk of minimum length covering each edge at least once can nevertheless be found in
polynomial time by solving the
route inspection problem.

The problem of finding a single simple cycle that covers each vertex exactly once, rather than covering the edges, is much harder. Such a cycle is known as a
Hamiltonian cycle, and determining whether it exists is
NP-complete.^{
[9]} Much research has been published concerning classes of graphs that can be guaranteed to contain Hamiltonian cycles; one example is
Ore's theorem that a Hamiltonian cycle can always be found in a graph for which every non-adjacent pair of vertices have degrees summing to at least the total number of vertices in the graph.^{
[10]}

The
cycle double cover conjecture states that, for every
bridgeless graph, there exists a
multiset of simple cycles that covers each edge of the graph exactly twice. Proving that this is true (or finding a counterexample) remains an open problem.^{
[11]}

## Graph classes defined by cycle

Several important classes of graphs can be defined by or characterized by their cycles. These include:

- Bipartite graph, a graph without odd cycles (cycles with an odd number of vertices)
- Cactus graph, a graph in which every nontrivial biconnected component is a cycle
- Cycle graph, a graph that consists of a single cycle
- Chordal graph, a graph in which every induced cycle is a triangle
- Directed acyclic graph, a directed graph with no directed cycles
- Line perfect graph, a graph in which every odd cycle is a triangle
- Perfect graph, a graph with no induced cycles or their complements of odd length greater than three
- Pseudoforest, a graph in which each connected component has at most one cycle
- Strangulated graph, a graph in which every peripheral cycle is a triangle
- Strongly connected graph, a directed graph in which every edge is part of a cycle
- Triangle-free graph, a graph without three-vertex cycles

## See also

- Cycle space
- Cycle basis
- Cycle detection in a sequence of iterated function values

## References

- ^
^{a}^{b}^{c}^{d}Bender & Williamson 2010, p. 164. **^**Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces",*Graph Theory and Its Applications*(2nd ed.), CRC Press, pp. 197–207, ISBN 9781584885054.**^**Diestel, Reinhard (2012), "1.9 Some linear algebra",*Graph Theory*, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28.**^**Tucker, Alan (2006). "Chapter 2: Covering Circuits and Graph Colorings".*Applied Combinatorics*(5th ed.). Hoboken: John Wiley & sons. p. 49. ISBN 978-0-471-73507-6.- ^
^{a}^{b}Sedgewick, Robert (1983), "Graph algorithms",*Algorithms*, Addison–Wesley, ISBN 0-201-06672-6 **^**Silberschatz, Abraham; Peter Galvin; Greg Gagne (2003).*Operating System Concepts*. John Wiley & Sons, INC. pp. 260. ISBN 0-471-25060-0.**^**GeeksforGeeks: Shortest cycle in an undirected unweighted graph**^**Veblen, Oswald (1912), "An Application of Modular Equations in Analysis Situs",*Annals of Mathematics*, Second Series,**14**(1): 86–94, doi: 10.2307/1967604, JSTOR 1967604.**^**Richard M. Karp (1972), "Reducibility Among Combinatorial Problems" (PDF), in R. E. Miller and J. W. Thatcher (ed.),*Complexity of Computer Computations*, New York: Plenum, pp. 85–103.**^**Ore, Ø. (1960), "Note on Hamilton circuits",*American Mathematical Monthly*,**67**(1): 55, doi: 10.2307/2308928, JSTOR 2308928.**^**Jaeger, F. (1985), "A survey of the cycle double cover conjecture",*Annals of Discrete Mathematics 27 – Cycles in Graphs*, North-Holland Mathematics Studies, vol. 27, pp. 1–12, doi: 10.1016/S0304-0208(08)72993-1.

- Balakrishnan, V. K. (2005).
*Schaum's outline of theory and problems of graph theory*([Nachdr.] ed.). McGraw–Hill. ISBN 978-0070054899. - Bender, Edward A.; Williamson, S. Gill (2010).
*Lists, Decisions and Graphs. With an Introduction to Probability*.