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 (x1, y1) and (x2, Y2) are adjacent iff |x1 -x2| <= 1 and ly1 - y2I <= 1.
The weight of an edge {(x1, y1), (x2, Y2)} is √ ((x1 - x2)2 + (y1 - y2)2).
What is the weight of a minimum weight-spanning tree in the graph?
a) n-1
b) n+1
c) n
d) log n