({{, (RefLink[TreeGraphQ, paclet:ref/TreeGraphQ])[g] 
yields (RefLink[True, paclet:ref/True]) if the graph g is a tree and (RefLink[False, paclet:ref/False]) otherwise.}})

OpenersNotesSection(Spacer1)Details

A tree is a connected graph with no cycles.

OpenersPrimaryExamplesSection(Spacer1)Examples  (19)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

Test whether a graph is a tree:

Graph[{1\[DirectedEdge]2,1\[DirectedEdge]3,2\[DirectedEdge]4,2\[DirectedEdge]5}]

TreeGraphQ[%]

CompleteKaryTree[2,2]

TreeGraphQ[%]

AdjacencyGraph[{{0,1,1},{0,0,0},{0,0,0}}]

TreeGraphQ[%]

A graph with cycles is not a tree:

CycleGraph[5]

TreeGraphQ[%]

OpenersExampleSection1(Spacer1)Scope  (6)

(RefLink[TreeGraphQ, paclet:ref/TreeGraphQ]) works with undirected graphs:

TreeGraphQ[]

Directed graphs:

TreeGraphQ[]

Multigraphs:

TreeGraphQ[]

Mixed graphs:

TreeGraphQ[]

(RefLink[TreeGraphQ, paclet:ref/TreeGraphQ]) gives (RefLink[False, paclet:ref/False]) for anything that is not a tree graph:

TreeGraphQ[x]

TreeGraphQ[Graph[garbage]]

(RefLink[TreeGraphQ, paclet:ref/TreeGraphQ]) works with large graphs:

g=GridGraph[{1,1000000}];

TreeGraphQ[g]//Timing

{VertexCount[g],EdgeCount[g]}

OpenersExampleSection4(Spacer1)Properties & Relations  (10)

A tree graph can be a simple graph:

CompleteKaryTree[2,3]

{TreeGraphQ[%],SimpleGraphQ[%]}

A tree graph can be a weighted graph:

CompleteKaryTree[2,3,VertexWeight->RandomInteger[5,4]]

{TreeGraphQ[%],WeightedGraphQ[%]}

A star is a special tree with as many leaves as possible:

StarGraph[10]

TreeGraphQ[%]

A path graph with no repeated vertices is a tree with two leaves:

GridGraph[{1,5}]

{PathGraphQ[%],TreeGraphQ[%]}

A graph with self-loops is not a tree graph:

Graph[{1\[UndirectedEdge]1,1\[UndirectedEdge]2}]

TreeGraphQ[%]

A graph with cycles is not a tree graph:

CycleGraph[3]

TreeGraphQ[%]

A disconnected graph is not a tree graph:

Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]1,4\[UndirectedEdge]5}]

{ConnectedGraphQ[%],TreeGraphQ[%]}

A tree graph with n vertices has n-1 edges:

CompleteKaryTree[3,3]

VertexCount[%]-EdgeCount[%]

A tree graph is a bipartite graph:

BipartiteGraphQ[CompleteKaryTree[3,3]]

A tree graph is not Hamiltonian:

HamiltonianGraphQ[CompleteKaryTree[3,3]]

OpenersExampleSection5(Spacer1)Possible Issues  (1)

(RefLink[TreeGraphQ, paclet:ref/TreeGraphQ]) gives (RefLink[False, paclet:ref/False]) for non-explicit graphs:

TreeGraphQ[CompleteKaryTree[n,m]]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[Graph, paclet:ref/Graph])  ▪  (RefLink[DirectedGraph, paclet:ref/DirectedGraph])  ▪  (RefLink[TreeGraph, paclet:ref/TreeGraph])  ▪  (RefLink[ConnectedGraphQ, paclet:ref/ConnectedGraphQ])  ▪  (RefLink[AcyclicGraphQ, paclet:ref/AcyclicGraphQ])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Graph Properties & Measurements, paclet:guide/GraphPropertiesAndMeasurements])}, {▪(RefLinkPlain[Graph Predicates and Properties, paclet:guide/GraphPredicates])}})}})