For two minimum spanning trees $T_1,T_2$, $\{c(e):e\in T_1\}=\{c(e): e\in T_2\}$

Question

Let $G$ be an undirected, edge weighted Graph. Do all minimum spanning trees $T$ of $G$ have the same signature $S_T:=\{c(e):e\in T\}$?
I think this is true, but I don't know how to prove this. Maybe with contradiction?
This means I assume that there exists another minimum spanning tree $T'$ with $S_T\neq S_{T'}$. Because $\sum_{e\in T}c(e)=\sum_{c\in T'}c(e)$, there exists $e_1,e_2\in T$ with $c(e_1)<c(e_3)$ and $c(e_2)>c(e_4)$ for some $e_3, e_4\in T$. Now I don't know how to lead it to a contradiction.

Answer 1

Now that I'm caught up, the answer is "yes". We can actually prove something stronger. I will work with spanning forests, rather than spanning trees, so that we don't have to concern ourselves with the graph being connected. We can also show that the sequence of weights used by the minimal spanning forests (i.e. not just the weights used, but the number of times they are used) is the same for all spanning forests.

Suppose $G = (V, E)$ is a finite, undirected, weighted graph. For $\alpha \in \Bbb{R}$, let $$G_\alpha = (V, E_\alpha), \qquad E_\alpha = \{e \in E : c(e) \le \alpha\}.$$ That is, $G_\alpha$ is the vertex-complete subgraph of $G$ containing edges of weight at most $\alpha$. Taking inspiration from Kruskal's algorithm, we show the following:

Proposition. Suppose $F$ is a minimal spanning forest of $G$ and $\alpha \in \Bbb{R}$. Then $F_\alpha$ is a minimal spanning forest of $G_\alpha$.

Proof. Clearly $F_\alpha$ is a forest, as it is contained in $F$.

Suppose it does not span $G_\alpha$. Then, $G_\alpha$ has fewer connected components than $F_\alpha$. That is, there exist $v_1, v_2 \in V$ such that a path $P$ in $G_\alpha$ exists between the two vertices, but no such path exists in $F_\alpha$. Since $F$ is spanning, another path $P'$ exists in $F$ that connects $v_1$ and $v_2$.

The paths $P$ and $P'$ are necessarily distinct, and so a cycle must exist in their union. This cycle must contain edges from both paths, meaning that it contains some edges exclusively from $F$, and some from exclusively from $G_\alpha$.

The former edges from $F$ have a weight strictly higher than $\alpha$, while the latter edges from $G_\alpha$ have a weight lower than or equal $\alpha$. If we remove from $F$ an edge from the former category, but replace it with an edge from the latter category, we once again get a spanning forest, but with strictly lesser weight, contradicting minimality. Thus, $F_\alpha$ is a spanning forest.

Finally, we show $F_\alpha$ is minimal. Let $G'$ be the vertex-complete graph formed by taking the edges of $F$, and adding in the rest of $E_\alpha$. Then, $G'$ is still a spanning subgraph, and any subgraph that spans $G'$ will span $G$. Note that $F$ is a minimal spanning tree of $G'$.

I claim that any edge from $F$, but not from $E_\alpha$, will be a bridge in $G'$ (i.e. removing it from $G'$ will increase the number of connected components). If this were not the case, then we could remove this edge from $F$, and replace it with an edge from $E_\alpha$, giving us a spanning forest of lesser weight than $F$. So, the claim is true.

Thus, any spanning forest of $G'$ must contain all edges from $F$ with weight greater than $\alpha$.

Take any spanning forest $H'$ of $G_\alpha$ (not necessarily $F_\alpha$), and extend it to a spanning forest of $G'$ (which must contain all the edges mentioned above). So, the weight of $H$ is the weight of $H'$, plus the total weights of these mandatory edges from $F$. The (minimal) weight of $F$ is the total weights of these mandatory edges, plus the weight of $F_\alpha$. If we could choose $H'$ with weight lesser than $F_\alpha$, then $H$ would have weight lesser than $F$, which is a contradiction. Thus, $F_\alpha$ is minimal, as required. $\,\large\square$

So, how do we use this proposition? We can prove what you want by induction on the number of distinct weights in the graph. A finite weighted graph will have a finite number of weights: $\alpha_1, \ldots, \alpha_n$, and so we proceed by induction on $n$.

Consider the $n = 1$ case. Suppose $G = (V, E)$ is a weighted graph with exactly one weight $\alpha_1$ for all edges. The weight sequence must be $\alpha_1$, repeated $|V| - 1$ times, regardless of which spanning tree is considered.

Suppose $k \in \Bbb{N}$ such that, for any finite, weighted graph with $k$ weights, any two spanning forests had the same weight sequences.

Further, suppose $G$ is a finite, weighted graph with $k + 1$ weights: $\alpha_1, \ldots, \alpha_{k+1}$. Assume without loss of generality that these weights are strictly increasing. Suppose further that $F$ and $F'$ are minimal spanning forests.

By the proposition, $F_{\alpha_k}$ and $F'_{\alpha_k}$ are both minimal spanning forests of $G_{\alpha_k}$, which is a graph of $k$ weights: $\alpha_1, \ldots, \alpha_k$. As such, the weight sequences of $F_{\alpha_k}$ and $F'_{\alpha_k}$ agree, by the induction hypothesis.

Note that $F$ and $F'$, as well as $F_{\alpha_k}$ and $F'_{\alpha_k}$, each have equal numbers of edges. This means that $F$ and $F'$ each contain the same number of new edges over $F_{\alpha_k}$ and $F'_{\alpha_k}$ respectively. If this number is $0$, then $F_{\alpha_k} = F$ and $F'_{\alpha_k} = F'$, and so we are done. Otherwise, a certain number of $\alpha_{k+1}$-weighted edges must be added to the weight sequence: the same for both $F$ and $F'$.

Thus, their weight sequences must be the same, and the result holds by induction.