2
$\begingroup$

A minimum spanning tree of an edge-weighted connected graph is a subset of the edges which connects all the vertices without any cycles and with the minimum possible edge weight.

Question: How is the matter of a minimum spanning tree handled for infinite graphs? Especially when the sum of weights is infinite?

Taking as an example the positive integers with the euclidean topology from the real line, and defining the weight of the edge connecting any two integers to be the distance between them, it is clear that any spanning tree will contain infinitely many edges of at least length one and therefore the total weight of any connected graph will always be infinite. On a prima facie basis one might conclude the weights of all spanning trees are incomparable and it's impossible to choose a minimum.

But a more compelling argument is that the minimum spanning tree is obviously the tree $M=(1,2),(2,3),(3,4),\ldots$

One can easily formalise this into a proof: pick any spanning tree $O$ other than $M$. Now $O$ will have at least two edges which overlap each other. Proceed by replacing each pair of overlapping edges in turn with either two or three consecutive edges which span the same points until you will arrive at $M$ by a proces of removing segments, hence $M<O$

So how is the matter of spanning weights typically handled when the sum of weights is infinite?

I can see that in the example above, a reasonable approach might be to form a function from the spanning graphs into the ordinals with $\omega$ representing the length of the real line and the length of the smallest spanning tree. Then $\omega+1$ is the length of the same tree but adjusted to have a single line segment of length one overlapping, e.g. by replacing $(1,2),(2,3)$ with $(1,3),(2,3)$.

$\endgroup$
6
  • 1
    $\begingroup$ I think that you are constantly using the word "vertex" where every graph theorist would use the word "edge". The spanning tree $M$ that you describe contains many edges, such as $(1,2)$ which join vertices, such as $2$. $\endgroup$ Commented Feb 19, 2022 at 22:43
  • $\begingroup$ Thanks @JamieRadcliffe corrected. $\endgroup$ Commented Feb 20, 2022 at 10:39
  • $\begingroup$ @MishaLavrov on the real line $[1,3)$ and $[2,3)$ is an example of a pair of edges which overlaps and could be replaced by $[1,2)$ and $[2,3)$ which do not overlap. Perhaps that example clarifies what I meant? I have used clopen sets here only so the statement is correct in topological terms as well as graph-theoretical terms. $\endgroup$ Commented Feb 20, 2022 at 10:40
  • $\begingroup$ Would an edge between $1$ and $4$ also overlap an edge between $2$ and $3$? That's what your intervals suggest, but I don't see what graph-theoretical concept it could refer to. Anyway, this is a minor detail; I agree that $M$ ought to be the MST, even if I don't follow your proof. $\endgroup$ Commented Feb 20, 2022 at 16:42
  • 1
    $\begingroup$ An alternate argument: replace every edge $(i,j)$ of another tree $O$ by the sequence of edges $(i,i+1), (i+1,i+2), \dots, (j-1,j)$. This does not change total weight. But now the result has all the edges of $M$, some of them occurring multiple times, which is worse than having all of them only once. $\endgroup$ Commented Feb 20, 2022 at 16:43

1 Answer 1

3
$\begingroup$

For finite graphs, minimum spanning trees are characterized by the following property: tree $T$ is an MST of $G$ if and only if, for every edge $vw \in E(G) \setminus E(T)$, no edge of the unique $v-w$ path in $T$ has a higher weight than $vw$. This is a property that we could easily generalize to infinite graphs; it only requires comparing edge costs one at a time.

There might not be an MST by this definition. Consider the complete graph on vertex set $\mathbb N$, and give each edge $ij$ the weight $\frac1{\max\{i,j\}}$. Then no spanning tree has the property described above. However, I also feel comfortable saying that this graph simply does not have an MST; no matter which spanning tree you pick, there is a better spanning tree.

$\endgroup$
4
  • 1
    $\begingroup$ In fact, I think your example has spanning trees whose edge weights have converging sum, and there are such trees with total edge weight less than any positive $\epsilon$. $\endgroup$
    – aschepler
    Commented Feb 19, 2022 at 23:01
  • $\begingroup$ Thank-you for this useful example of problems that may occur. I'm sorry to push for more but if I were to ask for a minimum spanning tree of the positive integers, with some p-adic metric as the weight (e.g. p=$2$), would this suffer the same fate as your $\frac1{\max\{i,j\}}$? Is your $\frac1{\max\{i,j\}}$ a metric / ultrametric / what? $\endgroup$ Commented Feb 20, 2022 at 10:58
  • $\begingroup$ (by fate, I mean no minimum spanning tree exists). I ask because I'm seeing a triangle-like inequality in the property you give in your first paragraph and I'm just thinking through what it is. $\endgroup$ Commented Feb 20, 2022 at 11:04
  • 1
    $\begingroup$ The example I gave just has weights decreasing enough that no matter what you do with the first $n$ node, you'll regret it when you get to later nodes. The same is not true for the $p$-adic weights. Say you're in the $2$-adic case. You'll need at least one edge between an even and an odd integer; this is an expensive edge, but there's not going to be a cheaper way to connect even and odd integers, so you might as well pay it once. So if you draw the edge $1$ to $2$ and never connect even and odd integers again, you will not regret that edge. Then we repeat on even and odd integers separately. $\endgroup$ Commented Feb 20, 2022 at 16:36

You must log in to answer this question.

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