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. A circuit is a non-empty trail in which the first and last vertices are equal (closed trail). Let G = (V, E, φ) be a graph. A circuit is a non-empty trail (e1, e2, ..., en) with a vertex sequence (v1, v2, ..., vn, v1). A cycle or simple circuit is a circuit in which only the first and last vertices are equal. A directed circuit is a non-empty directed trail in which the first and last vertices are equal (closed directed trail). Let G = (V, E, φ) be a directed graph. A directed circuit is a non-empty directed trail (e1, e2, ..., en) with a vertex sequence (v1, v2, ..., vn, v1). A directed cycle or simple directed circuit is a directed circuit in which only the first and last vertices are equal. 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.