Identify this graph problem. [Edit 01/02/2021] : Now the problem has been identified, as a relaxation of "minimal spanning tree" (it is more a minimal spanning sub-graph). Are they some references I could use on this problem ?
Let consider a graph made of $N$ nodes, numeroted from $B_1$ to $B_N$.
Each nodes can or cannot be connected to the other nodes, but overall we consider a family of weighed edges : $(\nu_{ij})_{1 \leq i < j \leq N} \in \mathbb{R}^{\frac{N(N-1)}{2}}$.
The edges must be understood as followed :

*

*$\nu_{ij}=0$ if $B_i$ and $B_j$ are not linked by an edge.


*there is no edge connecting one node to himself.
I want to operate with a specific way on this graph (I want to select some specific edges), and I believe I am looking for a family of numbers $(x_{ij})_{1 \leq i < j \leq N}$ with $x_{ij}=0$ or $1$ that verifies the following discrete optimization problem :
$$\underset{(x_{ij})_{1 \leq i < j \leq N} \in (0,1)^{\frac{N(N-1)}{2}}}{\min} \sum_{i<j}\  \nu_{ij} \  x_{ij}$$
with the following constraints on the $(x_{ij})$:

*

*$\sum_{i<j} x_{ij} = N-1$ (i.e we are only gonna keep $N-1$ edges in the graph)

*$\forall i \in \{1,\dots,N\}$, we have $$\sum_{j=i+1}^N x_{ij} + \sum_{j=1}^{i-1} x_{ji}  \geq 1$$ (i.e every nodes have at least one "non-zero" edge)

My questions
Is this problem known in operation research or discrete optimization or is it closed to a known problema with a theoritical analysis ? I don't know a lot of them, except for the traveling salesman problem or the cover set problem but I am quite unfamiliar with them.
Separately from this first question, I believe (heuristically, at least) that any family $(x_{ij})_{1 \leq i < j  \leq N}$ admissible for this problem verifies the following property :
the final graph with value $(x_{ij} \nu_{ij})$ on the edge is made of cycles and of only one path
But i am not sure how to prove it. I'have been looking for counter-examples using $4/5$ nodes and cycle but couldn't find any...
Any help, references or remarks are welcomed on the problem :).
 A: This is a relaxation of the minimum spanning tree (MST) problem.  The connectivity requirement of MST has been replaced with a "no isolated nodes" requirement in your problem.
A: (I assume here that your edges' costs are in $\mathbb R_+^* \cup \{+\infty\}$)
First, you can remove the $\Sigma x_{ij} = N+1$ constraint.
If you have a minimum-cost solution, it will be a forest covering all the nodes (since if there was a cycle, you could remove its biggest edge, and the "non-zero degree" constraint will still be preserved at a better cost).
Given this minimum-cost solution, if you want to add edges to add up to $N+1$ edges, you can use the smallest edges that aren't used yet.
So now you just need a minimum-size edge cover of the vertices, and this has a polynomial solution (see https://en.wikipedia.org/wiki/Edge_cover)
EDIT : The Wikipedia page only cites the problem with constant-valued edges. A polynomial solution also exists for the real-valued one : see [Plesník, Ján, Equivalence between the minimum covering problem and the maximum matching problem, Discrete Math. 49, 315-317 (1984). ZBL0581.05045.]
Concerning the shape of the solution, it turns out that, in this minimum-cost forest, you won't have a 3-length path. If you have a chain $u - v - w - x$ then the same forest without the $(u,v)$ edge still works for the constraints and has a lower cost. So the solution is a collection of trees whose diameter is 1 or 2 : those are stars (https://en.wikipedia.org/wiki/Star_(graph_theory)).
But then, you just fill it with the smallest edges you get, so you could have any graph shape.
