Proof on undirected graph/ minimal spanning tree

Question

I have an undirected simple graph $ G=(V,E)$ with $V= \{1,...,n\}$ and $ w: E \rightarrow \mathbb{R} , w(e_{ij}):=i+j$ I want to show, that $ (V,T)=(\{1,...,n\},\{ \{1,2\}, \{1,3\},....,\{1,n\}\})$ is a minimal spanning tree. How can I do that?

Answer 1

Suppose edge $e=\{i,j\}$ with $1<i<j$ belongs to a minimal spanning tree. Verify that the spanning tree must contain either a path from $1$ to $i$ not involving edge $e$ or a path from $1$ to $j$ not involving edge $e$.

In the first case replace edge $e$ by edge $\{1,j\}$, in the second case replace it by edge $\{1,i\}$. Verify that you still have a spanning tree.

Now you have contradicted the minimality of the original spanning tree.