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.
Best Answer
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.