WOLFRAM

Wolfram Language & System Documentation Center

AcyclicGraphQ[g]

yields True if the graph g is an acyclic graph and False otherwise.

Details
Details and Options Details and Options
Background & Context
Examples  
Basic Examples  
Scope  
Applications  
Properties & Relations  
Possible Issues  
See Also
Related Guides
History
Cite this Page

AcyclicGraphQ

AcyclicGraphQ[g]

yields True if the graph g is an acyclic graph and False otherwise.

Details

  • A graph has a cycle if there is a path that starts and ends in the same vertex.

Background & Context

  • AcyclicGraphQ checks if a graph is cycle-less. A graph cycle (more properly called a circuit when the cycle is identified using an explicit path with specific endpoints) is a subset of a graph's edge set that forms a connected path such that the first node of the path corresponds to the last. A graph with no cycles is known as an acyclic graph, while a graph containing one or more cycles is called a cyclic graph. AcyclicGraphQ returns True for an acyclic graph (ignoring any self-loops) and False otherwise.
  • A simple graph containing no cycles of length three is called a triangle-free graph, and a simple graph containing no cycles of length four is called a square-free graph. Simple acyclic graphs are therefore triangle-free and square-free. They are also non-Hamiltonian (i.e. they contain no Hamiltonian cycles).
  • A connected acyclic graph is known as a tree. All trees are therefore acyclic by definition, and TreeGraphQ (which is equivalent to the logical conjunction of AcyclicGraphQ and ConnectedGraphQ) can be used to check if a graph is a tree. Trees appear extensively in computer science and in particular in the implementation of many types of algorithms and data structures, including file and folder storage on disk.
  • A not-necessarily-connected acyclic graph is known as a forest. A forest with directed edges is more commonly known as a directed acyclic graph or DAG. A DAG is therefore a graph for which both AcyclicGraphQ and DirectedGraphQ return True. DAGs are important in modeling many different kinds of information, e.g. electronic circuits, information flows, and events and tasks.
  • FindCycle can be used to find one or more cycles in graphs that are not acyclic (and returns the empty list {} for graphs that are).

Examples

open all close all

Basic Examples  (2)

Test whether a graph is acyclic:

Wolfram Language code: GraphData[{"CayleyTree", {3, 4}}]
Wolfram Language code: AcyclicGraphQ[%]

Not all graphs are acyclic:

Wolfram Language code: PetersenGraph[5, 2]
Wolfram Language code: AcyclicGraphQ[%]

Scope  (6)

AcyclicGraphQ works with undirected graphs:

Wolfram Language code: AcyclicGraphQ[[image]]

Directed graphs:

Wolfram Language code: AcyclicGraphQ[[image]]

Multigraphs:

Wolfram Language code: AcyclicGraphQ[[image]]

Mixed graphs:

Wolfram Language code: AcyclicGraphQ[[image]]

AcyclicGraphQ gives False for expressions that are not graphs:

Wolfram Language code: AcyclicGraphQ[x]

AcyclicGraphQ works with large graphs:

Wolfram Language code: GridGraph[{10, 10, 10, 10}];
Wolfram Language code: AcyclicGraphQ[%]//Timing

Applications  (1)

A condensation graph is acyclic:

Wolfram Language code: g = [image];

The vertices of the condensation are the strongly connected components:

Wolfram Language code: c = ConnectedComponents[g]
Wolfram Language code: HighlightGraph[g, Subgraph[g, #]& /@ c]

Construct the condensation graph:

Wolfram Language code: vout = Complement[VertexOutComponent[g, #], #]& /@ c;
Wolfram Language code: m = Table[Boole[Intersection[v, s] != {}], {v, vout}, {s, c}];
Wolfram Language code: AdjacencyGraph[c, m, VertexShapeFunction -> "Name", EdgeStyle -> Arrowheads[.1]]

Verify that it is acyclic:

Wolfram Language code: AcyclicGraphQ[%]

Properties & Relations  (6)

Use DepthFirstScan to detect cycles in a graph:

Wolfram Language code: g = [image];
Wolfram Language code: Catch[DepthFirstScan[g, {"BackEdge" -> (Throw[False]&)}];True]

Compare with AcyclicGraphQ:

Wolfram Language code: % == AcyclicGraphQ[g]

A CycleGraph is not acyclic:

Wolfram Language code: CycleGraph[5]
Wolfram Language code: AcyclicGraphQ[%]

A TreeGraph is acyclic:

Wolfram Language code: CompleteKaryTree[3, 3]
Wolfram Language code: {TreeGraphQ[%], AcyclicGraphQ[%]}

A PathGraph with different start and end vertices is acyclic:

Wolfram Language code: PathGraph[Range[25]]
Wolfram Language code: {PathGraphQ[%], AcyclicGraphQ[%]}

An acyclic graph is not Hamiltonian:

Wolfram Language code: HamiltonianGraphQ[CompleteKaryTree[3, 3]]

A graph with minimal vertex degree greater than 2 is not acyclic:

Wolfram Language code: g = GridGraph[{2, 3}]
Wolfram Language code: VertexDegree[g]
Wolfram Language code: AcyclicGraphQ[g]

Possible Issues  (1)

AcyclicGraphQ ignores self-loops:

Wolfram Language code: g = [image];
Wolfram Language code: LoopFreeGraphQ[g]
Wolfram Language code: AcyclicGraphQ[g]
Wolfram Research (2010), AcyclicGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/AcyclicGraphQ.html.

Text

Wolfram Research (2010), AcyclicGraphQ, Wolfram Language function, https://reference.wolfram.com/language/ref/AcyclicGraphQ.html.

CMS

Wolfram Language. 2010. "AcyclicGraphQ." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/AcyclicGraphQ.html.

APA

Wolfram Language. (2010). AcyclicGraphQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/AcyclicGraphQ.html

BibTeX

@misc{reference.wolfram_2026_acyclicgraphq, author="Wolfram Research", title="{AcyclicGraphQ}", year="2010", howpublished="\url{https://reference.wolfram.com/language/ref/AcyclicGraphQ.html}", note=[Accessed: 13-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_acyclicgraphq, organization={Wolfram Research}, title={AcyclicGraphQ}, year={2010}, url={https://reference.wolfram.com/language/ref/AcyclicGraphQ.html}, note=[Accessed: 13-June-2026]}