Editing Cycle (graph theory) (section)

== Chordless cycle ==
[[File:Graph with Chordless and Chorded Cycles.svg|thumb|right|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.]]

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 graph|complement]] of a graph hole. Chordless cycles may be used to characterize [[perfect graph]]s: 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 (graph theory)|girth]] of a graph is the length of its shortest cycle; this cycle is necessarily chordless. [[Cage (graph theory)|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.