10
$\begingroup$

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!?!

$\endgroup$
  • $\begingroup$ wiki.answers.com/Q/… $\endgroup$ – dato datuashvili Feb 5 '14 at 10:33
  • 1
    $\begingroup$ A tree is a type of graph. A spanning tree is a subgraph of the graph that is a tree and hits every vertex. $\endgroup$ – Ian Coley Feb 5 '14 at 10:33
16
$\begingroup$

"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).

$\endgroup$
  • $\begingroup$ To complete the list, you might add a spanning subgraph that is not a tree - for example the cyclic graph formed by the outer edges $\endgroup$ – Hagen von Eitzen Feb 5 '14 at 10:47
  • $\begingroup$ Sure, why not. (Added.) $\endgroup$ – Rebecca J. Stones Feb 5 '14 at 10:53
  • $\begingroup$ @RebeccaJ.Stones can we conclude Every Spanning tree is a tree while every tree is not necessarily a spanning tree $\endgroup$ – laura Oct 3 '17 at 6:45
  • $\begingroup$ We can conclude the first part (every spanning tree is a tree) by definition. The second part sounds a bit weird. Trivially, every tree is a spanning tree of itself, but we usually think of a graph G and look at spanning trees of G (and not just think of "spanning trees" by themselves). $\endgroup$ – Rebecca J. Stones Oct 3 '17 at 7:26
2
$\begingroup$

A tree is just a type of graph (connected and no cycles).

You can only say that $G$ is a spanning graph of $H$: it's more of a relation between graphs, which states a few things at the same time: $G$ is a subgraph of $H$ (i.e. it has a subset of the vertices and a subset of the edges), $G$ is a tree when considered on its own (as above), and it is spanning (the set of vertices of $G$ actually equals the vertices of $H$). So it says three things, of which two are about the relation between them. Saying it is a tree is simpler and has less information.

$\endgroup$
1
$\begingroup$

The only difference is the word 'spanning', a kind of 'skeleton' which is just capable to hold the structure of the given graph $G$. Infact, there may be more than one such 'skeletons' in a given graph but a tree $T$ has the only one i.e. $T$ itself.

$\endgroup$
0
$\begingroup$

Spanning tree is a maximal tree subgraph or maximal tree of graph G (i.e. A tree T is said to be a spanning tree of a connected graph G if T is a subgraph of G and T contain all vertices of G.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.