The minimum sum of the absolute differences of adjacent nodes in an acyclic graph

Question

When I'm doing my computer science programming assignment, I'm asked to minimize the sum of all the absolute differences between adjacent nodes in a Binary Search Tree by rearranging the nodes, from which I come up with a mathematical problem in graph theory.

What is the minimum value of the sum of all absolute differences of all adjacent nodes in all possible acyclic and connected graph formed by $m$ nodes, where each node is associated with a value from a given set of real numbers $\{x_n\}_{0\leq n\leq m}$ with distinct values ($i\neq j\Leftrightarrow x_i\neq x_j$), and all the values from the set are used?

Obviously, the very first trial is to link the nodes linearly such that the values are in ascending order, in which the sum of absolute differences is $\text{max}\{x_n\}-\text{min}\{x_n\}$. Although it is quite certain, I am not sure whether this is the minimum sum, and I am not sure how to prove or disprove this.

Since I am new to graph theory, I converted the problem into another problem.

Given a set of $m$ real numbers $\{x_n\}_{0\leq n\leq m}$ with distinct values ($i\neq j\Leftrightarrow x_i\neq x_j$), prove or disprove that $$\sum_{i\neq j, \text{ all elements in }\{x_n\}_{0\leq n\leq m}\text{ must appear in the sum},\text{ total number of terms is } m-1}|x_i-x_j|\geq \text{max}\{x_n\}-\text{min}\{x_n\}$$

But it seems that this does not help a lot. I would like to ask what I should do to prove this. Thanks!

Edit: The original question is clarified. The graph is acyclic and connected. The set of real numbers are given, and we are asked to try all possible graphs and find the minimum sum.

Answer 1

For a graph $G$, we let $f(G)$ denote the sum of the absolute differences as defined in the question.

Claim 1. Let $G$ be an optimal graph (that is, $G$ achieves the smallest possible value of the sum of absolute differences). Then for each vertex $y$ in $G$ that has two neighbours $z_1$ and $z_2$, we must have $z_1 < y < z_2$ or $z_1 > y > z_2$.

Remark: The claim above does not specify $y$ has exactly two neighbours. The claim holds even if the vertex has more than two neighbours.

Proof. Without loss of generality, assume $z_1 > z_2$. Then it suffices to show that $z_1 > y > z_2$.

We know that either $y > z_1 > z_2$ or $z_1 > y > z_2$ or $z_1 > z_2 > y$ must be true.

• If $y > z_1 > z_2$, consider the graph $G'$ obtained by removing the edge $(y, z_2)$ and adding the edge $(z_1, z_2)$. We can see that $G'$ is still connected and acyclic. (Why? Drawing a diagram might help.) Furthermore, $$f(G') = f(G) - (y - z_2) + (z_1 - z_2) = f(G) - (y - z_1) < f(G)$$ which contradicts the assumption that $G$ is an optimal graph.
• If $z_1 > z_2 > y$, consider the graph $G'$ obtained by removing the edge $(y, z_1)$ and adding the edge $(z_1, z_2)$. Again, we see that $G'$ is connected and acyclic, and $$f(G') = f(G) - (z_1 - y) + (z_1 - z_2) = f(G) - (z_2 - y) < f(G)$$ which is also a contradiction.

Therefore, we must have $z_1 > y > z_2$. $\square$

With this claim, we can prove one of your guesses.

Claim 2. The optimal graph is a path graph, i.e., no node has degree more than $2$.

Proof. Suppose otherwise. That is, suppose that in an optimal graph $G$, there exists a vertex whose degree is at least $3$. Let the value assigned to this vertex be $y$.

Observe that either $y$ is larger than at least two of the neighbouring vertices, or $y$ is smaller than at least two of the neighbouring vertices. (Why? Hint: If both are false, can the degree of the vertex be at least $3$?) Either way, due to Claim 1, we know $G$ is not an optimal graph. $\square$

Armed with these two claims, it is relatively straightforward to find an optimal graph. (Hint: Use the triangle inequality; for all real numbers $x$, $y$, and $z$, we have $|x - y| + |y - z| \geq |x - z|$.)