Skip to main content
added 102 characters in body; added 94 characters in body
Source Link
Tony Huynh
  • 32.6k
  • 11
  • 115
  • 189

I think the answer is no for both questions. Take a cycle Let $T$ be the unique tree on $n$$2n$ vertices, with two adjacent vertices $u$ and let each edge have$v$ of degree $n$. Let $e=uv$. Let the weight of $n/2$$e$ be $n^2$ and all other edges to have weight 0. Then every minimum weight spanning treethe sum of all the average weights is

$n^2/n + n^2/n = 2n = |V(T)|$.

However, $T$ has total weight $n(n-1)/2$$n^2$, which is not $O(n^2)$$O(2n)$.

EditComment. Sorry,I edited my first answer as I misread the condition on the average degrees.

I think the answer is no for both questions. Take a cycle on $n$ vertices, and let each edge have weight $n/2$. Then every minimum weight spanning tree has weight $n(n-1)/2$, which is $O(n^2)$.

Edit. Sorry, I misread the condition on the average degrees.

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.

Source Link
Tony Huynh
  • 32.6k
  • 11
  • 115
  • 189

I think the answer is no for both questions. Take a cycle on $n$ vertices, and let each edge have weight $n/2$. Then every minimum weight spanning tree has weight $n(n-1)/2$, which is $O(n^2)$.

Edit. Sorry, I misread the condition on the average degrees.