Cycle (graph theory)

In graph theory, a cycle is a special path in a graph where you can start at a point and return to it by moving along connected lines or edges, without repeating any edge along the way except for the first and last points, called vertices. Imagine a map with cities connected by roads; a cycle would be a route that lets you leave a city and come back to it through a different path.

In a directed graph, where the connections between points have a specific direction, like one-way streets, a directed cycle follows the same idea but only moves in the allowed directions. This means you can follow the one-way streets and return to your starting city without going against any traffic rules.

Graphs without cycles are called acyclic graphs. When a directed graph has no directed cycles, it is known as a directed acyclic graph. If a connected graph has no cycles at all and is like a tree branching out from one point, it is called a tree. Understanding cycles helps us study networks, plan routes, and solve many problems in computer science and mathematics.

Definitions

A circuit is a path in a graph where you start at a point and end at the same point, visiting some points in between. Think of it like a loop in a playground where you begin and finish at the same spot.

A cycle is a special kind of circuit where, besides the start and end points being the same, all the other points are different. The length of a cycle is just how many steps or connections it has. In directed graphs, where paths have a specific direction, these ideas work the same way but follow the direction of the paths.

Chordless cycle

A chordless cycle in a graph, also called a hole, is a special kind of path where only the starting and ending points are the same, and there are no extra connections between points on the cycle. These cycles help us understand perfect graphs, which follow special rules about their shape.

The girth of a graph is the length of its smallest cycle, which is always chordless. There are also special graphs called cages, which are the smallest regular graphs with specific properties.

Cycle space

The term cycle can also mean an element of the cycle space of a graph. The most common cycle space is called the binary cycle space. It includes groups of connections where each point has an even number of connections. These groups behave like a vector space.

According to Veblen's theorem, every part of the cycle space can be made by combining simple cycles without sharing connections. A cycle basis is a selection of simple cycles that covers the entire cycle space. This idea can also be expanded using concepts from algebraic topology to work with different types of numbers.

Cycle detection

In graph theory, we can find out if a graph has a cycle by using a method called depth-first search (DFS). If during this search we find an edge that points back to a vertex we already visited, that means there is a cycle. For undirected graphs, we only need to look at vertices connected to the current one, skipping the one we came from to avoid counting short, trivial cycles.

We can also use other methods, like topological sorting, to spot cycles. In directed graphs, cycles can only happen within certain parts of the graph called strongly connected components. There are also special algorithms for finding cycles in very large graphs spread across many computers, which work by sending messages that should return to the sender if there’s a cycle. These tools help detect problems like deadlocks in computer systems.

One way to use DFS to find a cycle is to mark each vertex as we visit it. If we reach a vertex that’s already been marked but not finished, we know there’s a cycle. For undirected graphs, we skip the vertex that led us to the current one to avoid false alarms. We can also use breadth-first search to find the smallest cycle possible.

Covering graphs by cycle

In 1736, Leonhard Euler showed that a graph can have a walk that uses every edge exactly once if it is connected and each vertex has an even number of edges. This special walk is called an Eulerian trail. For directed graphs, a similar rule applies: the graph must be strongly connected with equal numbers of incoming and outgoing edges at each vertex.

Finding a cycle that visits each vertex exactly once, known as a Hamiltonian cycle, is much more difficult. One important result, Ore’s theorem, guarantees that such a cycle exists in certain graphs. The cycle double cover conjecture, still unsolved, suggests that every bridgeless graph can be covered by cycles in a special way.

Graph classes defined by cycle

Some special types of graphs are defined by the cycles they contain or don’t contain. For example, a bipartite graph has no cycles with an odd number of vertices. A cycle graph is made up of just one cycle.

Other graphs are special because they have no cycles at all, like a forest, or because every cycle has certain properties, like a chordal graph, where every cycle forms a triangle. These different rules about cycles help mathematicians study and classify graphs in many useful ways.