Allen Career Institute: Spanning tree

Question

Let $G$ be a simple undirected complete and weighted graph with vertex set $V = {0, 1, 2, …. 99.}$ Weight of the edge $(u, v)$ is $\left | u-v \right |$ where $0\leq u, v\leq 99$ and $u\neq v$. Weight of the corresponding maximum weighted spanning tree is______________

---

Doubt:Here asking for maximum weight spanning tree. So, there weight will be $0$ to every node. Isnot it? but answer given 7351.   

Answer 1

Answer :-

Comments

See

if there are n vertex and also n edge , there is atleast 1 cycle

right?

Here in ur answer also some possibility of forming cycle

So, how do u determine, that those cycle will not be formed? or ur graph free from those cycle?

---

if there are n vertex and also n edge , there is atleast 1 cycle

Yes. 

 So, how do u determine, that those cycle will not be formed? or ur graph free from those cycle?

Apply the prim's algorithm on the 2nd graph which is in the given answer with relaxation after removing each vertex from min-heap.. This algo takes care of loop.. Right? 

---

yes, I got it, by taking small example like 1 to 9

but very difficult with primes