A spanning tree of a graph \( G \) is a sub-graph which includes all the vertices of \( G \) and is also a tree.