In a graph with $n$ vertices every two vertices are connected by a unique path. For each two vertices $u$ and $v$, let $d(u, v)$ denote the distance between $u$ and $v$, i.e. the number of edges in the path connecting these two vertices, and $\deg(u)$ denote the degree of a vertex $u$. Let $W$ be the sum of pairwise distances between the vertices, and $D$ the sum of weighted pairwise distances: $\sum_{\{u, v\}}(\deg(u)+\deg(v))d(u, v)$. Prove that $D=4W-n(n-1)$.
Problem
Source: Tuymaada 2023 Senior P2
Tags: combinatorics
IAmTheHazard
07.07.2023 21:16
The unique path condition implies the graph is a tree, now induct by removing a leaf $v$ (base case trivial). After some algebraic manipulations we want to show that $$\sum_{w} (2-\mathrm{deg}(w))d(v,w)=n-1.$$This is by induction again, treating our leaf as a "root" and adding leaves on (base case trivial again). If we add a new leaf $w'$ attached to $w$, then $(2-\mathrm{deg}(w))d(v,w)$ decreases by $d(v,w)$ and the new term $(2-\mathrm{deg}(w'))d(v,w')$ increases by $d(v,w')$, which is actually just $d(v,w)+1$, so we're done.
Tintarn
08.07.2023 16:40
IAmTheHazard wrote: After some algebraic manipulations we want to show that $$\sum_{w} (2-\mathrm{deg}(w))d(v,w)=n-1.$$ Actually, once you prove this, you don't need induction anymore: Just sum this over all $v$. Done.
MrezaAttaran
30.12.2023 15:29
Easily we obtain $G$ is a tree. For every edge $e$ if we delete $e$ the graph will be divided into two separate trees $A_e$ and $B_e$.With a easy double counting we have \[ W = \sum_{e \in E(G)}^{} |A_e|\cdot|B_e| \]. And if we put weight $w_e = |B_e| \cdot \sum_{v \in A_e}^{} \mathrm{deg}(v) + |A_e|\cdot \sum_{v \in B_e}^{} \mathrm{deg}(v)$ on edge $e$ then \[ D = \sum_{e \in E(G)}^{} w_e \]Using the fact that $A_e$ and $B_e$ are trees we can compute $\sum_{v \in A_e}^{} \mathrm{deg}(v)$ and $\sum_{v \in B_e}^{} \mathrm{deg}(v)$ and with attention to $|A_e| = n-|B_e|$ we can finish the solution.