Talk:Spanning tree (mathematics)

From Wikipedia, the free encyclopedia

[edit] Definition

The definition of "spanning forest" given here is not the usual one in graph theory. Usually a spanning forest is any forest which is a subgraph and whose vertices include all the vertices of the graph. Even the subgraph which has all of the vertices but no edges at all is a spanning forest. --McKay 15:04, 27 August 2006 (UTC)

I'm not sure about that. Such a definition doesn't seem as useful. For example, this paper maintains a spanning forest of a graph as edges and vertices are added and deleted, which would of course be trivial if it had the definition you give. Every other reference I found, at least in computer science, was also using it in this sense. I'd like to see a citation for your definition. Deco 23:16, 27 August 2006 (UTC)

Your suggestion that it is different in computer science seems to be correct. As far as (mathematical) graph theory is concerned, usually "spanning forest" is taken to be the conjunction of "spanning subgraph" and "forest"; i.e., any spanning subgraph that happens to be a forest. Most graph theory books (I looked at about 8-9) don't give a separate definition. Searching for "spanning forest" at arXiv gives 18 papers of which all but 1 seem to use this definition. Of course the solution to this problem is to give both definitions. I think we are fairly safe in saying that one is common in computer science and the other is common in graph theory. --McKay 14:13, 28 August 2006 (UTC)