Question 10084 –

Consider a graph whose vertices are points in the plane with integer co-ordinates (x,y) such that 1≤x≤n and 1≤y≤n, where n≥2 is an integer. Two vertices (x₁,y₁) and (x₂,y₂) are adjacent iff ∣x₁−x₂∣ ≤ 1 and ∣y₁–y₂∣ ≤1. The weight of an edge {(x₁,y₁),(x₂,y₂)} is √(x₁–x₂)² + (y₁–y₂)²
(a) What is the weight of a minimum weight-spanning tree in this graph? Write only the answer without any explanations.

(b) What is the weight of a maximum weight-spanning tree in this graph? Write only the answer without any explanations.

Correct Answer: A