[Math] Difference between a tree and spanning tree?!

graph theory

I'm unable to understand the difference between a tree and a spanning tree. A tree is a graph that is connected and contains no circuits. A spanning tree of a graph G is a tree that contains every node of G. So what is the difference!?!

Best Answer

"Spanning" is the difference: a spanning subgraph is a subgraph which has the same vertex set as the original graph. A spanning tree is a tree (as per the definition in the question) that is spanning.

For example:

enter image description here

has the spanning tree

enter image description here

whereas the subgraph

enter image description here

is not a spanning tree (it's a tree, but it's not spanning). The subgraph

enter image description here

is also not a spanning tree (it's spanning, but it's not a tree).

Related Question