Let $G$ be a non-oriented connexe graph made of $N$ nodes $B\_i$. We suppose that they are not any self-connected node.

For every $(i,j) \in \{1, \dots, N \}$, we note $\nu\_{ij} \geq 0$ a positive weigth on the associated edge $ij$. If $\nu\_{ij}=0$, that simply means that the nodes $B\_i$ and $B\_j$ are not really connected by an edge.

For a collection of real $(b\_{ij})\_{1 \leq i<j \leq N}$, consider the following problem of optimization :

\begin{equation}
\min\_{(u\_1,\dots,u\_N) \in \mathbb{R}^N} \sum\_{i=1}^N \sum\_{j=1}^{i-1}
 |b\_{ij}+u\_i-u\_j| \nu\_{ij}
\tag{1}
\end{equation}
Solving this problem is equivalent to cut some edges out of the graph $G$, the idea is to chose well the coefficient $u\_i$ so as to erase the biggest contributions $\nu\_{ij}$. **I would like to prove that the edges which are going to be 'erased' (i.e the edges such as $|b\_{ij}+u\_i-u\_j|=0$) are exactly the edges of a maximal spanning tree $T$ of $G$.**

I recall here the defitinition of a maximal spanning tree :

A graph $T=((B\_i)\_{1 \leq N},A\_T)$ is said to be a maximal spanning tree of $G$ if for every $(i,j) \in (1, \dots, N)$, the edge $ij$ has a weight of $x\_{ij} \nu\_{ij}$, with the $(x\_{ij})\_{1 \leq i < j \leq N}$ be a solution of :

\begin{align}
\max\_{x\_{ij} \in (0,1)^{\frac{N(N-1)}{2}}} \sum\_{i=1}^N \sum\_{j=1}^{i-1} x\_{ij} \nu\_{ij}
\tag{2}
\end{align}
with the following constraints :

* the graphe formed with coefficient $x\_{ij} h\_{ij}$ has no cycle in it
* $$\sum\_{j=i+1}^N x\_{ij} + \sum\_{j=1}^{i-1} x\_{ji} \geq 1, \quad \forall i \in \{1,\dots,N \}$$

These two conditions insures that the graph obtained with coefficient $x\_{ij} \nu\_{ij}$ is indeed a tree.

Remark that I'm not sure that the result I want to prove is true. I'have tried this construction on several little graphs but I found no counter-example, but I'm not very used to graph theory. Any remarks or advices are welcomed.