A graph cycle of a finite simple graph 
is a closed walk of length at least
3 whose vertices are distinct except that the first
and last are the same. It is also called a circuit when
the first vertex is not specified. The incidence
vectors of graph cycles generate a vector
space over the two-element finite field. A basis for this space is called a cycle
basis.
A cycle that uses each graph vertex of a graph exactly once is called a Hamiltonian cycle.
A graph containing no cycles of length three is called a triangle-free graph, and a graph containing no cycles of length four is called a square-free graph.
A graph containing no cycles of any length is known as an acyclic graph, whereas a graph containing at least one cycle is called a cyclic graph. A graph possessing exactly one (undirected, simple) cycle is called a unicyclic graph. A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest.
The length of the shortest graph cycle (if any) in a given graph is known as the girth, and the length of a longest cycle is known as the graph circumference.
Any cycle of a graph can be expressed as a sum modulo 2 over a fundamental cycle set of the graph (Gould 1959, Paton 1969).
The minimum number of swaps between vertices in a random circular embedding of a cycle to put in its standard configuration is considered by Björner and Wachs (1982) and (Stanley 1999).
An acyclic graph is bipartite, and a cyclic graph is bipartite iff all its cycles are of even length (Skiena 1990, p. 213).
The number of closed 
-walks in a graph with adjacency
matrix 
,
counted with a specified starting vertex and direction
of traversal, is 
,
where 
denotes the matrix
trace. To obtain the number 
of undirected 
-cycles, subtract the closed 
-walks that are not cycles and divide
by 
. By analogy with the matching-generating
polynomial and independence polynomial,
a cycle polynomial whose coefficients count cycles
of each length is defined in this work. This use differs from polynomials associated
with cycle indices of permutation
groups, which are also called cycle polynomials.
For a simple graph, the number 
of undirected 
-cycles with 
is related to the matrix
of counts of paths 
by
 |
(1)
|
where 
denotes the matrix trace and 
is the adjacency matrix
(Voropaev and Perepechko 2012).
Graphs corresponding to closed walks of length 
are known as k-cyclic graphs, or "
-graphs"
for short. The numbers of 
-graphs for 
, 4, ... are 1, 3, 3, 10, 12, 35, 58, 160, 341, 958, 2444,
7242, 21190, 67217, 217335, ... (OEIS A081809;
FlowProblems).
Harary and Manvel (1971) gave the following closed forms for small 
:
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
 |  |  |
(8)
|
(with 
variants from Voropaev and Perepechko), where 
is the number of edges of the graph,
denotes the 
element of 
, 
is the matrix formed from the diagonal elements of 
, and 
is the 
th vertex degree. Alon et
al. (1997) extended these results up to 
, although with explicit
formulas given only up to 
. Exact formulas for 
and 
are given by
 |  |  |
(9)
|
 |  |  |
(10)
|
where 
is the 
th
vertex degree (Voropaev and Perepechko 2012; S. Perepechko,
pers. comm., Jan. 4, 2014).
Khomenko and Golovko (1972) gave a formula giving the number of cycles of any length, but its computation requires computing and performing matrix
operations involving all subsets up to size 
, making it computationally expensive. A simplified and improved
version of the Khomenko and Golovko formula is given by
 |
(11)
|
for 
, 4, ..., 
, where 
is the 
th matrix power of the submatrix
of the adjacency matrix 
with the subset 
of rows and columns deleted (Voropaev and Perepechko 2012).
The case 
therefore gives the number of Hamiltonian cycles.
Giscard et al. (2019) gave the formula for the number of undirected 
-cycles in a graph 
as
 |
(12)
|
where the sum is over connected induced subgraphs 
of 
, 
denotes the set of neighbors
of 
in 
(namely vertices 
of 
which are not in 
and such that there exists at least one edge from 
to a vertex
of 
), 
denotes the matrix trace,
and 
is the 
th matrix power of the adjacency
matrix of the graph 
.
Let 
denote the total number of undirected
cycles in a graph and 
the circuit rank. Then
 |
(13)
|
(Kirchhoff 1847, Ahrens 1897, König 1936, Volkmann 1996). The total numbers of undirected cycles for all simple graphs of orders 
, 2, ... are 0, 0, 1, 13, 143, 1994, 39688, ... (OEIS A234601).
In particular, a connected graph is unicyclic iff 
.
Equivalently, this occurs iff its edge
count equals its vertex count.
 |
(14)
|
iff any two cycles have no edge in common (Volkmann 1996). Among connected graphs,
the equality therefore holds for (and only for) cactus
graphs. Mateti and Deo (1976) proved that there are "essentially" only
four graphs with 
: the complete graphs 
and 
, the complete bipartite
graph 
,
and 
(Volkmann 1996).
For a graph of positive graph order 
,
the total number of undirected cycles also satisfies
 |
(15)
|
and
 |
(16)
|
where 
is the number of vertices and 
is the minimum vertex
degree (Volkmann 1996).
The following table gives the number of undirected graph cycles for various classes of graphs. The lists
for complete graphs, crown
graphs, cycle graphs, prism
graphs, and web graphs begin at 
. The 
-crossed prism graph
and triangular graph lists begin at 
, and the wheel graph list
begins at 
.
All other lists begin at 
.
An X indicates that the family is not defined for the corresponding parameter value.
| graph | OEIS | sequence |
| Andrásfai graph | A234602 | 0, 1, 29, 1014, 72273, 9842527, ... |
| antiprism graph | A077263 | X, X, 63, 179, 523, 1619, 5239, 17379, ... |
| bishop graph | A234636 | 0, 0, 3, 106, 17367, 24601058, 638520866656, ... |
 -black bishop graph | A234603 | 0, 0, 2, 53, 12424, 12300529, ... |
cocktail
party graph  | A167987 | 0, 1, 63, 2766, 194650, 21086055, 3257119761, ... |
complete bipartite graph  | A070968 | 0, 1, 15, 204, 3940, 113865, 4662231, ... |
complete tripartite graph  | A234616 | 1, 63, 6705, 1960804, 1271288295, 1541975757831, ... |
complete graph  | A002807 | 1, 7, 37, 197, 1172, 8018, ... |
 -crossed
prism graph | A234617 | 28, 107, 380, 1345, 4878, 18219, ... |
| crown graph | A234618 | 1, 28, 586, 16676, 674171, 36729512, ... |
| cube-connected cycle graph | X, X, 2664, ... | |
cycle
graph  | A000012 | 1, 1, 1, 1, 1, 1, 1, 1, ... |
| folded cube graph | A234619 | 0, 0, 7, 204, 322248, ... |
grid graph  | A140517 | 0, 1, 13, 213, 9349, 1222363, 487150371, ... |
grid graph  | A234620 | 0, 28, 3426491, ... |
| halved cube graph | A234621 | 0, 0, 7, 2766, 4678134804, ... |
| Hanoi graph | 1, 11, 1761, ... | |
hypercube
graph  | A085408 | 0, 1, 28, 14704, 51109385408, ... |
 -king graph | A234622 | 0, 7, 348, 136597, 545217435, 21964731190911, ... |
 -knight graph | A234623 | 0, 0, 1, 222, 128769, 959427728, ... |
 -ladder graph | A000217 | 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, ... |
Möbius
ladder  | A020873 | X, X, 15, 29, 53, 95, 171, 313, 585, ... |
| Mycielski graph | A234625 | 0, 0, 1, 337, 445228418, ... |
| odd graph | A301558 | 0, 1, 57, 872137842, ... |
| permutation star graph | 0, 0, 1, 5442, ... | |
prism graph  | A077265 | 14, 28, 52, 94, 170, ... |
 -queen
graph | A234626 | 0, 7, 8215, 2080941496, 269529670654115055, ... |
rook graph  | A234624 | 0, 1, 312, 3228524, 6198979538330, ... |
| Sierpiński gasket graph | A234634 | 1, 11, 1033, ... |
| sun graph | A234627 | X, X, 11, 44, 198, 1036, 6346, 45019, 364039, ... |
sunlet
graph  | X, X, 1, 1, 1, 1, 1, 1, 1, 1, ... | |
| triangular graph | A234629 | 0, 1, 63, 15703, 58520309, ... |
| web graph | A077265 | 14, 28, 52, 94, 170, 312, 584, 1114, ... |
wheel graph  | A002061 | 7, 13, 21, 31, 43, 57, ... |
 -white
bishop graph | A234630 | X, 0, 1, 53, 4943, 12300529, ... |
Closed forms for some of these classes of graphs are summarized in the following table.
![1/2sum_(k=3)^(n)(k-1)!(n; k)=1/4n[2_3F_1(1,1,1-n;2;-1)-n-1]](/images/equations/GraphCycle/Inline128.svg)
-Graphs."