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= Σ min( degu,degv ) ∀(u,v)∈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 105 , then what it would be equal to? Can you share your thoughts on this ?
No cycles? So you mean the graph is a forest and m <= n-1 ? Please correct me if I'm wrong.
O sorry, my bad. It may conatin cycles. The main point is that the number of edges is bounded by 105.
O(m∗√m)
which is achieved in a complete graph, but I think op is more interested in the proof
Yeh, I too thought of it, but didn't got any proof for it. Can you please share how can it be so?
Separate vertices in to two sets
1) With degree >=√m. Maximum size of this set will be √m
2) With degree <=√m
Sum of contributions of all edges where at least one endpoint lies in second set will be at max m∗√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 ∑(deg[u]∗bdeg[u]) since bdeg[u]<=√m, contribution becomes ∑(deg[u]∗√m), if we pull the √m outside the summation then √m∗∑(deg[u])<=√m∗m