> > 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. >
In the problem, there are no constraints on the cardinality of the subgraphs. It could have a subgraph with all nodes (e.g. if the graph is a binary tree). Bruno On Thu, May 15, 2008 at 2:42 AM, Geoffrey Summerhayes <[EMAIL PROTECTED]> wrote: > > 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 -~----------~----~----~----~------~----~------~--~---
