# Spanning tree

## Definition

"... a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges."
https://en.wikipedia.org/wiki/Spanning_tree
"A spanning tree of a graph on n vertices is a subset of n-1 edges that form a tree (Skiena 1990, p. 227)."
http://mathworld.wolfram.com/SpanningTree.html
A spanning tree of an undirected graph on n vertices is a subset of n-1 edges that form a tree.

## Sage

Given an undirected graph, what are its spanning trees?
http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph.html#sage.graphs.graph.Graph.spanning_trees

## Sage

Given an undirected graph, how many spanning trees does it have?