A cycle of a graph 
, also called a circuit if the
first vertex is not specified, is a subset of the edge set
of 
that forms a path
such that the first node of the path corresponds to the last. A maximal set of edge-disjoint
cycles of a given graph 
can be obtained using ExtractCycles[g]
in the Wolfram Language package Combinatorica`
.
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 (undirected) closed 
-walks in a graph with adjacency
matrix 
is given by 
,
where 
denotes the matrix
trace. In order to compute the number 
of 
-cycles,
all closed 
-walks
that are not cycles must be subtracted. One would think that by analogy with the
matching-generating polynomial,
independence polynomial, etc., a cycle
polynomial whose coefficients are the numbers of cycles of length 
would be defined. While no such polynomial seems not to have
been defined in the literature (instead, "cycle polynomials" commonly instead
refers to a polynomial corresponding to cycle indices
of permutation groups), they are defined in
this work.
The number of 
-cycles
is related to the matrix of path counts
by
 |
(1)
|
where 
denotes the matrix trace and 
is the adjacency matrix
(Perepechko and Voropaev).
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 (1972) gave the following closed forms for small 
:
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
 |  |  |
(8)
|
(with 
variants from Perepechko and Voropaev), 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)
|
where 
is the 
th
vertex degree (Perepechko and Voropaev; 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
 |
(10)
|
for 
, 4, ..., 
, where 
is the 
th matrix power of the submatrix of the adjacency matrix 
with the subset 
of rows and columns deleted (Perepechko and Voropaev). The
case 
therefore gives the number of Hamiltonian
cycles.
Giscard et al. (2016) gave the formula for the number of undirected 
-cycles in a graph 
as
 |
(11)
|
where the sum is over connected induced subgraphs 
of 
,
denotes the number 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
 |
(12)
|
(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).
 |
(13)
|
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).
The total number of undirected cycles also satisfies
 |
(14)
|
and
 |
(15)
|
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.
| 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 | X, 0, 3, 106, 17367, 24601058, 638520866656, ... |
 -black bishop graph | A234603 | X, X, X, 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 | A000000 | 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 | X, 1, 13, 213, 9349, 122236, 487150371, ... |
grid graph  | A234620 | X, 28, 3426491, ... |
| halved cube graph | A234621 | 0, 0, 7, 2766, 4678134804, ... |
| Hanoi graph | A000000 | 1, 11, 1761, ... |
hypercube
graph  | A085408 | 0, 1, 28, 14704, 51109385408, ... |
 -king graph | A234622 | X, 7, 348, 136597, 545217435, 21964731190911, ... |
 -knight graph | A234623 | X, 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 | A000000 | 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  | A000000 | 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, X, X, 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/Inline116.svg)
-Graphs."