graph theorytrees
Is this claim true?
I thought about it and it seems true but for proving it i started with one direction by assuming that i have one minimum spanning tree and i want to show that from this i have also one maximum spanning tree.
Can i claim from having one minimum spanning tree the weight of every edge is different and then use this proof Show that there's a unique minimum spanning tree if all edges have different costs ?
The claim is false.
Consider a graph $G$ with points $a,b,c,d,e$ and edges $(a,b),(b,c),(c,d),(d,e),(e,a),(a,d)$ where all edges have weight 1, except $(a,b)$ and $(a,e)$ which have weight 100. Then there is only one minimum spanning tree, namely $(b,c),(c,d),(d,e),(a,e)$.
If instead the claim was the following: "If a graph $G$ is a cycle, and two of the edges $e_1$ and $e_2$ have weight $w$ which is the maximum weight in $G$, then there are at least two different minimum spanning trees in $G$"
Then the claim is true. Consider some spanning tree $T$ in $G$. Since $T$ is spanning, one of the edges, lets say $e_1$ with weight $w$ must be in $T$. Now consider a new tree $T' = T - e_1 + e_2$. Now one can easily show that $T'$ is also spanning and has the same weight as $T$.
The cut property of the Minimum Spanning Tree (MST) problem is what you should look at. i.e. Any edge $\{x,y\}$ in an MST has weight at least as small as the edge with smallest weight in the cut that separates $x$ and $y$. This can easily be shown by contradiction.
In any cut which includes the edge $e$ (i.e. separates it's two adjacent vertices), we know that $e$ must be an edge with minimum weight in this cut.
Any spanning tree $G'$ must contain at least one edge in this cut.
Let $e'$ be such an edge. We know that $$w(e') \ge w(e)$$ We also know that $$w(j) \ge w(e')$$ So, $$w(j) \ge w(e') \ge w(e)$$
Best Answer
It's not true.
Let $G$ be $K_n$ and let $P$ be a Hamilonian path in $G=K_n$. [Say $i$ and $j$ are adjacent in $P$ iff $|i-j|=1$, then two vertices $i$ and $j$ are adjacent in $G \setminus E(P)$ iff $|i-j| \ge 2$. One can check that $G \setminus E(P)$ is connected for $n \ge 6$ and has many cycles.]
Give every edge in $P$ a weight of 100 and every edge in $G \setminus E(P)$ a weight of 1. Then $G$ has one maximum-weight spanning tree--namely $P$, but many minimum spanning trees; indeed $G \setminus E(P)$ is connected and has many cycles so any spanning tree of $G \setminus E(P)$ is a minimum spanning tree, and $G \setminus E(P)$ has more than one spanning tree.