Bissoy.com
Doctors Medicines MCQs Q&A

For every spanning tree with n vertices and n edges what is the least number of different Spanning trees can be formed?

For every spanning tree with n vertices and n edges what is the least number of different Spanning trees can be formed? Correct Answer 3

If graph is connected and has ‘n’ edges, there will be exactly one cycle, if n vertices are there. A different spanning tree can be constructed by removing one edge from the cycle, one at a time. The minimum cycle length can be 3. So, there must be at least 3 spanning trees in any such Graph. Consider a Graph with n = 4, then 3 spanning trees possible at maximum (removing edges of cycle one at a time, alternatively). So, any Graph with minimum cycle length ‘3’ will have at least 3 spanning trees.

Related Questions

Which of the following statements regarding tree are correct? (A) All the links of a tree together does not constitute the complement of the corresponding tree (B) A connected subgraph of a connected graph is a tree if there exist (n - 1) nodes of the group (C) A connected subgraph of a connected graph is a tree if there exist many paths between any pair of nodes in it (D) The number of terminal nodes of end vertices of every tree are atleast two (E) Every connected graph has atleast one tree Choose the correct answer from the options given below: (1) (A) and (B) only (2) (B) and (C) only (3) (B) and (D) only (4) (D) and (E) only
Consider the with different types of trees. Sohan has different types of trees in the field which are given in the table below: Names of trees Number of trees Neem ||| Papaya |||| Mango |||| || Coconut |||| Guava ||| Using the table, answer the question Neem, Papaya and Mango trees together is how many more than Coconut and Guava trees together?
Consider the undirected graph below: Using Prim's algorithm to construct a minimum spanning tree starting with node a, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?
One-sixth of the trees in a garden are neem trees. Half of the trees are Ashoka trees and the remaining are eucalyptus trees. If the number of neem trees is five, then how many eucalyptus trees are there in the garden?
One-sixth of the trees in a garden are jamun trees, half of the trees are Eucalyptus trees and the remaining are peepal trees.  If the number of jamun trees is 6, how many peepal tree are there in the garden? 
There is a statement followed by two conclusions. Decide which conclusion logically follows from the given statement (s). Statement: A garden has mango, teak, neem, orange, coconut and many trees. The mango tree is 7 meters tall, the orange tree is half of its height and the coconut tree is three times the height of the mango tree. Conclusion: I. The average height of the three trees is less than 10 meters. II. The tallest tree in the garden is the coconut tree. Choose the correct option from the following. A. Only (I) follows. B. Only (II) follows. C. (I) and (II) both follow. D. Neither (I) nor (II) follows.
Let G be any connected, weighted, undirected graph. I. G has a unique minimum spanning tree, if no two edges of G have the same weight. II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight edge crossing the cut. Which of the above two statements is/are TRUE?
Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode. typedef struct treeNode* treeptr; struct treeNode {              treeptr leftMostChild, rightSibling; }; int DoSomething (treeptr tree) {              int value=0;              if (tree != NULL) {              if (tree->leftMostChild == NULL)              value = 1;    else               value = DoSomething(tree->leftMostChild);               value = value + DoSomething(tree->rightSibling);     }               return(value); } When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the 
A gardener has to plant trees in rows containing equal number of trees. If he plants in rows of 6, 8, 10 or 12 then five trees are left unplanted. But if he plants in rows of 13 trees each, then no tree is left. What is the number of trees that the gardener plants ?
In the following question, there are six parts marked S1, S6, P, Q, R and S. The position of S1 and S6 are fixed. Some parts of the sentence have been jumbled up. Rearrange these parts and choose the proper sequence from the given options. (S1) Once upon a time, there lived a farmer in a village, beside a forest. (P) When the farmer was a little boy, he spent much of his time playing with the apple tree (Q) Those days, the apple tree had given the choicest of apples to him (R) However, as time passed, the apple tree became old and stopped bearing fruits (S) He had a big garden that had an old apple tree and other plants, trees and beautiful flowers (S6) Now that the farmer was not getting any apples from the tree, he decided that the tree was useless and cut it.