Minimum and maximum of sum of inverse degree of a graph

Question

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

1. Is there any closed form of $D$ for general graph that involves $|V|$?
2. If not is there any tight lower bound on the sum?
3. Can we claim something like that the $D \geq |V|/k$ where k is a constant and $k<<|V|$?

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

Answer 1

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$.

---

Yulval'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.