# Spanning tree

Jump to navigation
Jump to search

Let be a connected graph. A Spanning Tree of graph is a subgraph of with vertex set and which is itself a Tree.
i.e:- simple connected acyclic graph. **OR** Given a undirected, unweighted, connected graph , Spanning tree of is the subgraph that covers all the vertices without forming a loop. If the graph is not connected, it forms a spanning forest.