Minimum spanning tree of a weighted graph I have a connected graph $G=(V,E)$ in $n$ vertices. The edge weights are non-negative and form a metric space, thus for vertices $u,v,w \in V$ , such that $(u,v), (v,w), (w,u)\in E$ we have $r(u,w) \leq r(u,v)+r(v,w)$. We furthermore have the following condition: $\sum_{u\in V}R(u) \leq n$ where $R(u)$ is the average of the weights of the edges incident on $u$.
My question is, does there exist a minimum spanning tree, that has weight at most $Cn$ where $C$ is some universal constant? In place of a minimum weight spanning tree, a walk (sequence of connected vertices) such that the sum of weights of the walk is $Cn$ for some universal constant.
 A: I think the answer is no for both questions.  Let $T$ be the unique tree on $2n$ vertices with two adjacent vertices $u$ and $v$ of degree $n$.  Let $e=uv$.  Let the weight of $e$ be $n^2$ and all other edges to have weight 0.  Then the sum of all the average weights is 
$n^2/n + n^2/n = 2n = |V(T)|$. 
However, $T$ has total weight $n^2$, which is not $O(2n)$.  
Comment. I edited my first answer as I misread the condition on the average degrees.  
A: You need some variant of the degree-constrained GMST (Generalized Minimum Spanning Tree) with edges satisfying the triangle inequality.  These are some pointers to literature.

*

*Bruce Boldon, Narsingh Deo and Nishit Kumar. Minimum-weight
degree-constrained spanning tree
problem

The minimum spanning tree problem
with an added constraint that no
node in the spanning tree has the
degree more than a specified
integer, $d$, is known as the
minimum-weight degree-constrained
spanning tree ($d$-MST) problem. Such
a constraint arises, for example, in
VLSI routing trees, in backplane
wiring, or in minimizing
single-point failures for
communication networks. The $d$-MST
problem is NP-complete. Here, we
develop four heuristics for
approximate solutions to the problem
and implement them on a
massivelyparallel SIMD machine,
MasPar MP-1. An extensive empirical
study shows that for random graphs
on up to 5000 nodes (about 12.5
million edges), the heuristics
produce solutions close to the
optimal in less than 10 seconds. The
heuristics were also tested on a
number of TSP benchmark problems to
compute spanning trees with a degree
bound $d = 3$.



*MR1469650 (98h:68181)  Fekete,
Sándor P.;  Khuller, Samir;
Klemmstein, Monika;  Raghavachari,
Balaji;  Young, Neal. A
network-flow technique for finding
low-weight bounded-degree spanning
trees. J. Algorithms  24  (1997),
no. 2, 310–324.


*MR1469648 (98d:68165)
Guttmann-Beck, Nili;  Hassin,
Refael. Approximation algorithms
for min-max tree partition. J.
Algorithms  24  (1997),  no. 2,
266–286.


*MR2006103 (2004h:68154)  Hassin,
Refael;  Levin, Asaf. Minimum
spanning tree with hop restrictions.
Twelfth Annual ACM-SIAM Symposium on
Discrete Algorithms (Washington,
DC, 2001).  J. Algorithms  48
(2003),  no. 1, 220–238.


*MR2480226 (2010f:68072)  Srivastav,
Anand;  Werth, Sören.
Probabilistic analysis of the degree
bounded minimum spanning tree
problem. FSTTCS 2007: Foundations of
software technology and theoretical
computer science,  497–507, Lecture
Notes in Comput. Sci., 4855,
Springer, Berlin,  2007.
