Question $4[14$ marks$]$

Consider nine cities at locations $0$ to $8$ in the below network, and each undirected link represents a potential connecting pipeline between two cities. The number on each link represents the cost for building such a pipeline. If we want to build the pipeline system to connect all the nine cities, with the minimum cost, which pipelines should we choose to build in the below figure?

Please answer the following questions:

$1)$ What type of OR task can be used to address the above question? $[2$ marks$]$

$2)$ Please solve the above question directly. $($Please show the steps in form of sketches in your answer book$)[6$ marks$]$

$3)$ The above question can be formulated as an integer programming, please write down the formulation. $($You do not need to solve it$)[6$ marks$]$