# Find all spanning tree in a given graph

Is there a way I can generate all the spanning tree in the following graph:

Also, is there a way to insert the adjacency matrix, then I get an output of all possible spanning trees?
The adjacency matrix $$A = \left( \begin{matrix} 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 & 0 \end{matrix} \right)$$

• What have you tried so far? Have you written the adjacency matrix for this? Please, share such things with us so that we may help to better answer your question? Mar 9, 2021 at 7:42
• @CATrevillian Thank you, I add the adjacency matrix, but I don't know where to start to final all the possible spanning tree. Mar 9, 2021 at 7:56

am = {{0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0,
0, 1, 1, 0, 1}, {0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 1}};

g0 = UndirectedGraph[SimpleGraph @ AdjacencyGraph @ am,
VertexCoordinates -> Reverse @ CirclePoints[{1, Pi}, 6],
VertexLabels -> "Name"]


trees = Select[TreeGraphQ[Graph@#] &] @ Select[VertexCount @ # == 6 &]@
Subsets[EdgeList[g0], {5}];

Length @ trees

32


This matches what we should expect from Kirchhoff's Theorem:

Det[KirchhoffMatrix[g0][[2 ;;, 2 ;;]]]

32


We can also get the same number using IGSpanningTreeCount from IGraphM package:

<< IGraphM
IGSpanningTreeCount[g0]

32


These 32 trees fall into three isomorphic groups:

Length /@ Gather[Graph /@ trees, IsomorphicGraphQ]

{10, 16, 6}

Graph[#, VertexLabels -> Placed["Name", Center], VertexStyle -> White,
GraphLayout -> "LayeredEmbedding",
VertexShapeFunction -> (Disk[#, Offset[7]] &),
AspectRatio -> 1] & /@ trees // Multicolumn[#, 6] &


HighlightGraph[g0, #, GraphHighlightStyle -> "Thick"] & /@ trees //
Multicolumn[#, 6, Appearance -> "Horizontal"] &


• You are amazing! Thanks a lot. Mar 9, 2021 at 9:17
Mar 9, 2021 at 9:53
• Thank you @Adam and Mubarak for the kind words.
– kglr
Mar 9, 2021 at 9:58

Does the following what you want? First we create the graph from the adjacency matrix:

a = {{0, 1, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0}, {0, 1, 0, 1, 1, 0}, {0,
0, 1, 0, 1, 1}, {0, 0, 1, 1, 0, 1}, {1, 0, 0, 1, 1, 0}};


Then we create the spanning trees:

FindSpanningTree[{agr, #}, VertexLabels -> "Name"] & /@ Range[6]


• Thank you. But it does not generate all of them. But @Kglr solved it. Mar 9, 2021 at 9:17

I may as well add a way to construct the graph

g=Graph[Join[#\[UndirectedEdge]#+1&/@Range@5,{1\[UndirectedEdge]6,
3\[UndirectedEdge]5,4\[UndirectedEdge]6}]]


In general Mathematica has no good way to do this. Here's a naive method.

Trees on $$n$$ vertices have $$n-1$$ edges. For every length $$n-1$$ tuple of edges, is it a tree?

trees=Select[Tuples[EdgeList@g,{VertexCount@g-1}],TreeGraphQ@Graph@#&]


For the g in question, I find 3840 unique trees. Of course Subsets is appropriate as opposed to Tuples, which causes this confusion. Here's a neat way to find all isomorphic trees:

Module[{l={}},For[i=1,i<=Length@trees,++i,
If[And@@Table[Not@IsomorphicGraphQ[Graph@e,Graph@trees[[i]]],{e,l}],
AppendTo[l,trees[[i]]]
]];l]
`

which produces 3 unique-up-to-isomorphism trees.