On May 15, 12:07 am, pramod <[EMAIL PROTECTED]> wrote: > Geoff, > > How did you arrive at the V(V+1)/2 figure? >
V nodes in the graph, so V trees consisting of a single node. Then since the graph is given as connected, there must be a least one path between each pair of nodes. Even if there is more than one the shortest path must qualify as a tree. Node order doesn't matter, so V*(V-1)/2 is the count of those pairs. Given the conditions for the subgraphs, it's always possible to create a graph that limits the size of all the acceptable subgraphs to less than three nodes. So sum the two terms and reduce ---- Geoff --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
