Find all spanning tree in a given graph

Question

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) $$

Answer 1

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"] &

Answer 2

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}};
agr = AdjacencyGraph[a]

Then we create the spanning trees:

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

Answer 3

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.