Intereting Posts

Is $L^{p}$ space with alternate norm banach?
Why do we need to learn integration techniques?
“Intrinsic” treatment of projective spaces
The vanishing ideal $I_{K}(A\!\times\!B)$ is generated by $I_{K}(A) \cup I_{K}(B)$?
Find an abelian infinite group such that every proper subgroup is finite
Is it true that $\limsup \phi\le\limsup a_n$, where $\phi=\frac{a_1+…+a_n}n$?
Sum of closed spaces is not closed
Does convergence in probability imply a.s. convergence in a countable space?
chromatic number of a graph versus its complement
Prerequisites to study cohomology?
Scheme: Countable union of affine lines
Rewriting repeated integer division with multiplication
Reference request: Nonlinear dynamics graduate reference
$G$ is Topological $\implies$ $\pi_1(G,e)$ is Abelian
Almost complex structures on spheres

Show that there’s a unique minimum spanning tree (MST) in case the edges’ weights are pairwise different $(w(e)\neq w(f) \text{ for } e\neq f)$.

I thought that the proof can be done for example by contradiction, saying that we have $2$ different MST meaning that somewhere was possible to pick from more edges, so $w(e) = w(f)$ for $e\neq f$, contradiction. Apparently this is not correct.

How would you show that a graph has a unique MST if all edges have distinct weights?

- Which directed graphs correspond to “algebraic” diagrams?
- How to construct a k-regular graph?
- Problem of Graph connectivity with degree sequences
- Prove that the chromatic polynomial of a cycle graph $C_{n}$ equals $(k-1)^{n} + (k-1)(-1)^{n}$
- Why does this matrix have 3 nonzero distinct eigenvalues
- Prove that a simple graph with $2n$ vertices without triangles has at most $n^2$ lines.

- Non-isomorphic graphs with four total vertices, arranged by size
- How many ways can one paint the edges of a Petersen graph black or white?
- Maximum of the sum of cube
- How many 2-edge-colourings of $K_n$ are there?
- How is $L_{2}$ Minkowski norm different from $L^{2}$ norm?
- asymptotics of the expected number of edges of a random acyclic digraph with indegree and outdegree at most one
- Number of edge disjoint Hamiltonian cycles in a complete graph with even number of vertices.
- Partition a binary tree by removing a single edge
- Euler's formula for tetrahedral mesh
- Prove that the nuclear norm is convex

If $T_1$ and $T_2$ are *distinct* minimum spanning trees, then consider the edge of minimum weight among all the edges that are contained in *exactly one* of $T_1$ or $T_2$. Without loss of generality, this edge appears only in $T_1$, and we can call it $e_1$.

Then $T_2 \cup \{ e_1 \}$ must contain a cycle, and one of the edges of this cycle, call it $e_2$, is not in $T_1$.

Since $e_2$ is a edge different from $e_1$ and is contained in *exactly one* of $T_1$ or $T_2$, it must be that $w ( e_1 ) < w ( e_2 )$. Note that $T = T_2 \cup \{ e_1 \} \setminus \{ e_2 \}$ is a spanning tree. The total weight of $T$ is smaller than the total weight of $T_2$, but this is a contradiction, since we have supposed that $T_2$ is a minimum spanning tree.

**A proof using cycle property:**

Let $G=(V,E)$ be the original graph.

Suppose there are two distinct MSTs $T_1=(V,E_1)$ and $T_2=(V,E_2)$. Since $T_1$ and $T_2$ are distinct, the sets $E_1-E_2$ and $E_2-E_1$ are not empty, so $

\exists e\in E_1-E_2$.

Since $e\notin E_2$, adding it to $T_2$ creates a cycle. By *cycle property* the most expensive edge of this cycle (call it $e’$) does not belong to any MST. But

If $e’=e$ then $e’\in E_1$ (because $e\in E_1-E_2$)

If $e’\neq e$ then $e’\in E_2$

Both cases are contradicting with the fact that $e’$ is not in any MST.

The best explanation I found was on wikipedia,

Proof:

Assume the contrary, that there are two different MSTs A and B.

Since A and B differ despite containing the same nodes, there is at least one edge that belongs to one but not the other. Among such edges, let e1 be the one with least weight; this choice is unique because the edge weights are all distinct. Without loss of generality, assume e1 is in A.

As B is a MST, {e1} {\displaystyle \cup } \cup B must contain a cycle C.

As a tree, A contains no cycles, therefore C must have an edge e2 that is not in A.

Since e1 was chosen as the unique lowest-weight edge among those belonging to exactly one of A and B, the weight of e2 must be greater than the weight of e1.

Replacing e2 with e1 in B therefore yields a spanning tree with a smaller weight.

This contradicts the assumption that B is a MST.

More generally, if the edge weights are not all distinct then only the (multi-)set of weights in minimum spanning trees is certain to be unique; it is the same for all minimum spanning trees.[1]

- Limit of this recursive sequence and convergence
- Show that the dual norm of the spectral norm is the nuclear norm
- Is there a relation between $End(M)$ and $M$ under tensor products?
- if R is a commutative ring in which all the prime ideals are finitely generated then R is Noetherian
- Multivariate Normal Difference Distribution
- Banach Measures: total, finitely-additive, isometry invariant extensions of Lebesgue Measure
- Proof of Wolstenholme's theorem
- How to find a general sum formula for the series: 5+55+555+5555+…?
- Suppose $f:→$ is increasing but not neccessarily continuous ,show that there is some $x∈$ such that $f(x)=x$
- $m$ doesn't come in the sequence $a_n=$ iff m is a perfect square
- Positive operator is bounded
- How to prove $\int_1^\infty\frac{K(x)^2}x dx=\frac{i\,\pi^3}8$?
- Example of subgroup of $\mathbb Q$ which is not finitely generated
- ''Linear'' transformations between vector spaces over different fields .
- Infinum & Supremum: An Analysis on Relatedness