### aknov711's blog

By aknov711, history, 18 months ago,

Recently, I got stuck in this line of thoughts.. Given a graph with n nodes and m edges with no cycles and multiple edges. Consider the summation of minimum degrees of the two endpoints of every edge of the graph.

More formally, wann'a know bound for

S= $\Sigma$ min( $deg_u,deg_v$ ) $\forall (u,v) \in E$

What would it be assympotically equal to ? Definitely, one upperbound can be O(n*m) since the largest degree for any node can ne n-1.

Suppose if n and m both are of order $10^5$ , then what it would be equal to? Can you share your thoughts on this ?

• +8

 » 18 months ago, # |   0 No cycles? So you mean the graph is a forest and m <= n-1 ? Please correct me if I'm wrong.
•  » » 18 months ago, # ^ |   0 O sorry, my bad. It may conatin cycles. The main point is that the number of edges is bounded by $10^5$.
 » 18 months ago, # |   +3 $O(m*\sqrt m)$
•  » » 18 months ago, # ^ |   +3 which is achieved in a complete graph, but I think op is more interested in the proof
•  » » 18 months ago, # ^ |   0 Yeh, I too thought of it, but didn't got any proof for it. Can you please share how can it be so?
•  » » 18 months ago, # ^ | ← Rev. 2 →   +32 Separate vertices in to two sets1) With degree $>=\sqrt m$. Maximum size of this set will be $\sqrt m$2) With degree $<=\sqrt m$Sum of contributions of all edges where at least one endpoint lies in second set will be at max $m*\sqrt m$Now let's assume for any vertex 'u' in first set, $bdeg[u]$ is no of adjacent vertices that are also in first set.Then contribution is $\sum{(deg[u]*bdeg[u])}$ since $bdeg[u]<=\sqrt m$, contribution becomes $\sum{(deg[u]*\sqrt m)}$, if we pull the $\sqrt m$ outside the summation then $\sqrt{m}*\sum(deg[u]) <= \sqrt{m}*m$