<p>This question is not theoretical, it's about combinatorial meaning.</p>

<p>In graph theory there is a notion of <em>complexity</em> of a graph, which is equal to the number of spanning trees in a graph, which combinatorically simply means how much the graph is 'connected' (it is the way I understand it, is there any other combinatorial meaning? (there are different meanings of 'connectivity', including <em>algebraic connectivity</em>, which is second eigenvalue of Laplacian, but this one is more intuitive, as I think)). There is a fast algorithms to compute complexity of a given graph (look <a href="https://cstheory.stackexchange.com/questions/17419/count-the-number-of-spanning-trees-fast">here</a> for the discussion).</p>

<p>There is also a fast algorithm to compute the number of minimal spanning trees(MST) of a given  weighted graph (for more information read <a href="http://www14.informatik.tu-muenchen.de/konferenzen/Jass08/courses/1/pieper/Pieper_Paper.pdf" rel="nofollow noreferrer">this paper</a>).</p>

<p><strong>The question is:</strong> what does having several MST's mean in terms of graph and distances? </p>

<p>P.S. It certainly means that not all distances are different, but, maybe there is some property, which provides more interesting consequences?</p>

<p>Thank you!</p>

CC BY-SA 3.0
2013-06-25T01:47:12.540Z
It might be better to consider spanning forests rather than spanning trees if the aim is a combinatorial meaning.  Spanning forests lead naturally to a hereditary associated property.
András Salamon
CC BY-SA 3.0
2013-05-24T13:31:27.443Z
You can use different MST as base of some approximation and heuristics, and if we have many of them our chance is better to get closer to the optimal solution, also I think if graph has many MST, means diameter in some subgraphs of original one should not be too large.
Saeed
<graph-theory><co.combinatorics><spectral-graph-theory>
Graph has several MST what does it mean combinatorically?
user197284
# Graph has several MST what does it mean combinatorically?

(Asked by: username_0 on 2013-05-24)

This question is not theoretical, it's about combinatorial meaning.

In graph theory there is a notion of *complexity* of a graph, which is equal to the number of spanning trees in a graph, which combinatorically simply means how much the graph is 'connected' (it is the way I understand it, is there any other combinatorial meaning? (there are different meanings of 'connectivity', including *algebraic connectivity*, which is second eigenvalue of Laplacian, but this one is more intuitive, as I think)). There is a fast algorithms to compute complexity of a given graph (look [here](https://cstheory.stackexchange.com/questions/17419/count-the-number-of-spanning-trees-fast) for the discussion).

There is also a fast algorithm to compute the number of minimal spanning trees(MST) of a given weighted graph (for more information read [this paper](http://www14.informatik.tu-muenchen.de/konferenzen/Jass08/courses/1/pieper/Pieper_Paper.pdf)).

**The question is:** what does having several MST's mean in terms of graph and distances?

P.S. It certainly means that not all distances are different, but, maybe there is some property, which provides more interesting consequences?

Thank you!

**Tags:** graph-theory, co.combinatorics, spectral-graph-theory

> **Comments:**
> **username_2**: You can use different MST as base of some approximation and heuristics, and if we have many of them our chance is better to get closer to the optimal solution, also I think if graph has many MST, means diameter in some subgraphs of original one should not be too large.  
> **username_1**: It might be better to consider spanning forests rather than spanning trees if the aim is a combinatorial meaning.  Spanning forests lead naturally to a hereditary associated property.  

---

## 0 answers

