SpanningTree(G) returns a spanning tree of a connected graph G.

SpanningTree(G, r) returns a spanning tree of the connected component of G which contains vertex r.

SpanningForest(G) returns a spanning forest of the graph G.

By default, edge weights on G are ignored. To compute a minimal-weight spanning tree for a weighted graph, use MinimalSpanningTree.

A spanning tree for a graph G is a subgraph of G which contains all the vertices of G and is a tree.

A spanning forest for a graph G is a subgraph of G which contains all the vertices of G and is a forest.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{with}\left(\mathrm{SpecialGraphs}\right)\:$

$P≔\mathrm{PetersenGraph}\left(\right)$

$P≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 15\; edges}$

$\mathrm{T1}≔\mathrm{SpanningTree}\left(P\right)$

$\mathrm{T1}≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 9\; edges}$

$\mathrm{IsTree}\left(\mathrm{T1}\right)$

$\mathrm{true}$

$\mathrm{DrawGraph}\left(P\right)$

$\mathrm{DrawGraph}\left(\mathrm{T1}\right)$

$\mathrm{T2}≔\mathrm{SpanningTree}\left(P\,5\right)\:$

$\mathrm{Edges}\left(\mathrm{T1}\right)$

$\left\{\left\{1\,2\right\}\,\left\{1\,5\right\}\,\left\{1\,6\right\}\,\left\{2\,3\right\}\,\left\{2\,9\right\}\,\left\{4\,5\right\}\,\left\{5\,8\right\}\,\left\{6\,7\right\}\,\left\{6\,10\right\}\right\}$

$\mathrm{Edges}\left(\mathrm{T2}\right)$

$\left\{\left\{1\,2\right\}\,\left\{1\,5\right\}\,\left\{1\,6\right\}\,\left\{3\,4\right\}\,\left\{4\,5\right\}\,\left\{4\,10\right\}\,\left\{5\,8\right\}\,\left\{7\,8\right\}\,\left\{8\,9\right\}\right\}$

$G≔\mathrm{GraphUnion}\left(\mathrm{CycleGraph}\left(\left[1\,2\,3\right]\right)\,\mathrm{CycleGraph}\left(\left[4\,5\,6\right]\right)\right)$

$G≔\mathrm{Graph\; 3:\; an\; undirected\; graph\; with\; 6\; vertices\; and\; 6\; edges}$

$\mathrm{IsConnected}\left(G\right)$

$\mathrm{false}$

$\mathrm{SpanningTree}\left(G\,1\right)$

$\mathrm{Graph\; 4:\; an\; undirected\; graph\; with\; 6\; vertices\; and\; 2\; edges}$

$\mathrm{SpanningForest}\left(G\right)$

$\mathrm{Graph\; 5:\; an\; undirected\; graph\; with\; 6\; vertices\; and\; 4\; edges}$

The GraphTheory[SpanningForest] command was introduced in Maple 2021.

For more information on Maple 2021 changes, see Updates in Maple 2021.