Minimum and maximum of sum of inverse degree of a graph

Suppose we have a simple undirected graph $G(V,E)$, where $V$ and $E$ are the set of vertices and edges respectively. we denote $d(v)$ as the degree of a vertex $v \in V$. I am interested to find closed form or a tight bound of the following quantity

$$
D = \sum_{e=\{u,v\} \in E} \frac{1}{d(u)+d(v)}
$$

For example, suppose we have a complete graph with $n$ vertices. Then $D$ becomes $$ D = \frac{n(n-1)/2}{2(n-1)} = n/4$$.

For a path graph with $n$ vertices ($(n-1)$ edges) $D$ is $ \frac{(n-3)}{4}+2/3 $. My question is

• Is there any closed form of $D$ for general graph that involves $|V|$?

• If not is there any tight lower bound on the sum?

• Can we claim something like that the $D \geq |V|/k$ where k is a constant and $k

*Yuval conjectured that $D \geq 1−1/n$ for a connect graph with $n$ vertices.

Nice question!

There is no simple closed form of $D$ for general graphs that involves $|V|$ since $D$ can take at least two different values for any connected graph with more than 2 vertices. $D=1-\frac1{|V|}$ for a start graph and $D=\frac{|V|}4 > 1-\frac1{|V|}$ for a cycle graph. In fact, I would believe that the number of different values of $D$ for a graph of $n$ vertices grows exponentially with respect to $n$.

Yuval's tight lower bound

Claim: $D \geq 1−1/n$ for a connect graph with $n$ vertices, where the equality holds for and only for star graphs.

Proof. Let $G$ be a connect graph with $m$ edges. Since $G$ is connected, $m\ge n-1$, where the equality holds for and only for tree graphs. Let $e=\{u,v\}$ be an edge in $G$.
$$\begin{aligned}
d(u)+d(v) &= \Sigma_{s\in E,\, s \text { contains u}} 1 + \Sigma_{s\in E,\, s \text { contains v}} 1 \\
&= (1 + \Sigma_{s\in E,\, s \text { contains u},\, s\neq e} 1) + (1 + \Sigma_{s\in E,\, s \text { contains v},\, s\neq e} 1) \\
&= 2 + (\Sigma_{s\in E,\, s \text { contains u},\, s\neq e} 1 + \Sigma_{s\in E,\, s \text { contains v},\, s\neq e} 1) \\
&\le 2 + \Sigma_{s\in E,\, s\neq e} 1\\
&= 2 + (m -1)\\
&= m +1
\end{aligned}$$
The inequality above holds since the only edge that contains both $u$ and $v$ is $e$. The equality $d(u)+d(v)=m+1$ holds when every edge besides $e$ has a common vertex with $e$.

So,
$$
D = \sum_{e=\{u,v\} \in E} \frac{1}{d(u)+d(v)} \ge m\, \frac1{m+1} = 1 - \frac1{m+1} \ge 1-\frac1n
$$

The equality $D=1-\frac1n$ holds when there are $n-1$ edges in total and every two edge has a common vertex, which means the graph is a star graph.

There is no positive constant $k$ such that $D \geq |V|/k$, since $|V|/k$ goes to infinity while $1-1/|V|$ stays below 1 when $|V|$ goes to infinity.

StackExchange Computer Science Q#98474, answer score: 3