MathDB

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 Statement