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.