Spanning Tree

A spanning tree is a subset of Graph G, where every Vertex is connected using as few Edge as possible. This means a spanning tree never has Cycles and may have more than one possible spanning tree.

This gives it a sort of tree-like structure in many cases, hence it's name.

Excerpt from Geeks For Geeks

• A spanning tree does not exist for a Disconnected Graph.
• For a Connected Graph having N vertices then the number of edges in the spanning tree for that graph will be N-1.
• We can construct a spanning tree for a Complete Graph by removing E-N+1 edges, where E is the number of Edges and N is the number of vertices.
• Cayley’s Formula: states that the number of spanning trees in a complete graph with N vertices is
  • For example: , then the maximum number of spanning trees possible =

• Several path finding algorithms, such as Dijkstra’s algorithm and A* Search, internally build a spanning tree as an intermediate step.