A spanning graph

Computer Science Level 3

Given a weighted complete graph $G$ on the vertex set $(v_{1}, v_{2}, \ldots, v_{n})$ such that the weight of the edge $(v_{i}, v_{j})$ is $2|i-j|$ , what is the weight of a minimum spanning tree of $G$ ?

2

2n

2n-2

n-1

1 solution

Abhishek Sinha
Dec 5, 2015

A spanning tree on $n$ vertices has $n-1$ edges. Since the weights of the edges are at least $2$ , every spanning tree of the graph $G$ has weight at least $2n-2$ . This lower-bound is achieved when we simply create a spanning tree by joining vertex $v_i$ to the vertex $v_{i+1}$ for $i=1,2,\ldots, n-1$ .

A spanning graph

1 solution

0 pending reports