15
$\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$
2
  • $\begingroup$ wiki.answers.com/Q/… $\endgroup$ Feb 5, 2014 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, 2014 at 10:33

5 Answers 5

20
$\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$
4
  • $\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$ Feb 5, 2014 at 10:47
  • $\begingroup$ Sure, why not. (Added.) $\endgroup$ Feb 5, 2014 at 10:53
  • 1
    $\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, 2017 at 6:45
  • 1
    $\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$ Oct 3, 2017 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$
-1
$\begingroup$

A tree and a spanning tree are related concepts in graph theory, but they have different meanings.

  1. Tree:

    • In graph theory, a tree is an undirected graph that is connected and acyclic, meaning there are no cycles (closed loops) in the graph.
    • A tree with n vertices will have exactly n-1 edges, and there is a unique path between any pair of vertices.
    • Trees are commonly used in computer science and algorithms for hierarchical structures, such as binary trees and search trees.
  2. Spanning Tree:

    • A spanning tree of a connected, undirected graph is a subgraph that includes all the vertices of the original graph while still being a tree.
    • In other words, a spanning tree is a tree that spans or covers all the vertices of the original graph.
    • Spanning trees are useful in network design, where they can be employed to ensure connectivity without forming cycles.

In summary, while a tree is a specific type of graph with no cycles, a spanning tree is a subgraph of a connected graph that retains connectivity by spanning all the vertices. Every connected graph has at least one spanning tree.

$\endgroup$
1
  • 1
    $\begingroup$ Was this AI-generated? (It's not a very good answer either way; mostly you're just stating facts about trees and spanning trees without filtering for relevance and without addressing the root confusion. But it also seems like the sort of not-very-good answer that ChatGPT might give.) $\endgroup$ Feb 29 at 3:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .