Cycle (graph theory)

Cages are defined as the smallest regular graphs with given combinations of degree and girth.

[3] The existence of a cycle in directed and undirected graphs can be determined by whether a depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (i.e., it contains a back edge).

[6] The aforementioned use of depth-first search to find a cycle can be described as follows: where For undirected graphs, "neighbour" means all vertices connected to v, except for the one that recursively called DFS(v).

This omission prevents the algorithm from finding a trivial cycle of the form v→w→v; these exist in every undirected graph with at least one edge.

In his 1736 paper on the Seven Bridges of Königsberg,[7] widely considered to be the birth of graph theory,[8][9] 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.

[7] 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.

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.

[10] 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.

A graph with edges colored to illustrate a closed walk , H–A–B–A–H, in green; a circuit which is a closed walk in which all edges are distinct, B–D–E–F–D–C–B, in blue; and a cycle which is a closed walk in which all vertices are distinct, H–D–G–H, in red.
In this graph the green cycle A–B–C–D–E–F–A is chordless whereas the red cycle G–H–I–J–K–L–G is not. This is because the edge {K, I} is a chord.