Cycle (graph theory)

A cycle in graph theory is a path that starts at a point and ends at the same point. You can only pass each connection once, except for the start and end points, which are called vertices. Think of it like a trip between cities where you leave a city and return to it using different roads.

In a directed graph, where connections have a set direction like one-way streets, a directed cycle follows paths that only go the allowed way. This means you can travel along one-way streets and return to your starting city without breaking 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 and spreads out from one point like branches, it is called a tree. Learning about cycles helps us understand networks, plan trips, and solve problems in computer science and math.

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. Imagine a loop in a playground where you begin and finish at the same spot.

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

Chordless cycle

A chordless cycle in a graph is a special path. It starts and ends at the same point, and there are no extra connections between the points on the path.

These cycles help us understand perfect graphs. Perfect graphs follow special rules about their shape.

The girth of a graph is the length of its smallest cycle. This smallest cycle is always chordless. There are also special graphs called cages. Cages are the smallest regular graphs with certain 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. 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.

Cycle detection

In graph theory, we can learn if a graph has a cycle by using a method called depth-first search (DFS). If 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 check vertices connected to the current one, skipping the one we came from.

We can also use other methods, like topological sorting, to find cycles. In directed graphs, cycles can only happen in special parts of the graph called strongly connected components. There are algorithms for finding cycles in very large graphs. These tools help find problems in computer systems.

One way to use DFS is to mark each vertex as we visit it. If we reach a vertex that’s already been marked, we know there’s a cycle. For undirected graphs, we skip the vertex that led us to the current one. 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. This walk is called an Eulerian trail. For directed graphs, a similar rule applies.

Finding a cycle that visits each vertex exactly once, known as a Hamiltonian cycle, is 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 have or don’t have. 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 rules about cycles help mathematicians study and organize graphs in useful ways.