# 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

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.

• If your graph is a star on $n$ vertices, $D=1-1/n$. – Yuval Filmus Oct 12 '18 at 0:33
• A tight lower bound involving only $|V|$ is zero: the graph could be empty. This also shows that $D$ doesn't depend just on $|V|$. – Yuval Filmus Oct 12 '18 at 0:59
• It looks like that Yuval's observation is sharp. Can you update your question to say that "Yuval conjectured that $D\ge 1- 1/n$ for a connect graph with $n$ vertices", assuming @YuvalFilmus does not mind? – John L. Oct 12 '18 at 4:13
• I certainly don't mind. It would also be interesting to find the maximum of $D$. – Yuval Filmus Oct 12 '18 at 4:20

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.