##### minimum weight-spanning tree

Consider a graph whose vertices are points in the plane with integer coordinates (x, y) such that 1 ≤ x ≤ n and 1 ≤ y ≤ n, where n ≥ 2 is an integer. Two vertices (x_{1}, y_{1}) and (x_{2}, y_{2}) are adjacent iff |x_{1} - x_{2}| ≤ 1 and |y_{1} - y_{2}| ≤ 1. The weight of an edge {(x_{1}, y_{1}), (x_{2}, y_{2})} is √((x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}). What is the weight of a minimum weight-spanning tree in the graph?

(A) n-1

(B) n

(C) n+1

(D) log n

**Answer**

Explain: (Answer- A)

## Pages