# FindCycle

FindCycle[g]

finds a cycle in the graph g.

FindCycle[g,k]

finds a cycle of length at most k in the graph g.

FindCycle[g,{k}]

finds a cycle of length exactly k.

FindCycle[g,{kmin,kmax}]

finds a cycle of length between kmin and kmax.

FindCycle[g,kspec,s]

finds at most s cycles.

FindCycle[{g,v},]

finds cycles that include the vertex v.

FindCycle[{vw,},]

uses rules vw to specify the graph g.

# Details • A cycle is also known as a circuit or loop.
• A cycle is a path with no repetitions of vertices or edges other than the starting and ending vertices.
• FindCycle gives a list of cycles. Each cycle is given as a list of edges.
• FindCycle will return an empty list if there is no cycle.
• FindCycle[g,kspec,All] finds all the cycles.
• For weighted graphs, FindCycle[g,k] gives all cycles with total weights less than k.
• FindCycle works with undirected graphs, directed graphs, and multigraphs.

# Background & Context

• FindCycle attempts to find one or more distinct cycles in a graph. Cycles are returned as a list of edge lists or as {} if none exist. A cycle of a graph (more properly called a circuit when the cycle is identified using an explicit path with particular endpoints) is a consecutive sequence of distinct edges such that the first and last edges coincide at their endpoints. Cycle enumeration can be used for planning a cyclic route in many situations (subway, road trip, etc.), computing voltage or current in electronic circuits, or discovering infinite loops in computer programs.
• In general, FindCycle[g,kspec,s] attempts to find s cycles of length kspec. The count specification s may be omitted (in which case it is taken to be 1), may be a positive integer, or can be All. The length specification kspec may be a positive integer k (in which case it stands for cycles of length k or less), Infinity, a positive integer inside a list {k} (in which case it stands for cycles of length exactly k), or a list of two positive integers {kmin,kmax} (in which case it stands for cycles of lengths kmin through kmax).
• A graph for which FindCycle[g,{3}] returns {} is known as a triangle-free graph, and one for which FindCycle[g,{4}] returns {} is known as square free. A cycle of length n, where n is the number of vertices in a graph, is known as a Hamiltonian cycle, and a graph possessing such a cycle is said to be Hamiltonian.
• A graph that does not contain any cycle is called an acyclic graph and can be tested for using AcyclicGraphQ.
• FindCycle returns simple cycles, while FindHamiltonianCycle, FindEulerianCycle, and FindFundamentalCycles return specific types of cycles. FindPath may be used to find a path (a set of edges for which the endpoints do not coincide) between two specific vertices, returned as a set of consecutive vertices along the path.

# Examples

open allclose all

## Basic Examples(2)

Find a cycle in a graph:

Highlight the cycle:

Find all cycles in a graph:

## Scope(12)

### Specification(6)

FindCycle works with undirected graphs:

Directed graphs:

Weighted graphs:

Multigraphs:

Use rules to specify the graph:

FindCycle works with large graphs:

### Enumeration(6)

A cycle of length exactly 8:

A cycle of length at most length 6:

A cycle of length between 3 and 5:

A cycle that includes a given vertex:

Find all cycles:

FindCycle gives an empty list if there is no cycle:

## Applications(4)

Find Hamiltonian cycles that visit each vertex exactly once:

Show the cycle:

Find cycles with a given property:

Include a vertex:

Include an edge:

Find the longest loops in the Korean Busan Underground:

The length of the longest loops:

Find the loops:

Plan a dog walk tour:

For a given starting node, find 5 tours of at least length 20 that avoid streets with bad dogs:

## Properties & Relations(3)

Use FindHamiltonianCycle to find cycles that visit each vertex exactly once:

Equivalent to:

EdgeCycleMatrix gives a basis for all cycles:

Build all cycles:

Find all cycles from FindCycle:

FindCycle gives an empty list for acyclic graphs:

## Possible Issues(1)

FindCycle ignores self-loops: