retagged by
564 views
2 votes
2 votes

Consider the following statements:

  1. Let T be a minimum spanning tree of a graph G. Then for any two vertices u and v the path from u to v in T is the shortest path from u to v in the graph G
  2. Suppose that average edge weight for a graph G is $A_{avg}$. Then the minimum spanning tree of G will have weight at most (n-1) $A_{avg}$. Where n is number of vertices in graph G.

Which of the above statements are true?

  1. Only I
  2. Only II
  3. both I and II
  4. None of these

plz give one one counter example of both option I & II

retagged by

1 Answer

Best answer
2 votes
2 votes

Best way to approach this kind of question is provide counter examples.


I   

selected by

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
2
Vikas123 asked Dec 14, 2018
1,608 views
What we do if graph is complete with 5 vertices and weight are1,2,3,4,5,6,7,8,9 and 10.than find maximum possible weight that a minimum weight spanning tree of G have..??...
0 votes
0 votes
1 answer
3
atulcse asked Jan 13, 2022
476 views
How many minimum spanning trees are possible in this graph?
1 votes
1 votes
1 answer
4
Ram Swaroop asked Jan 30, 2019
1,562 views
Consider a simple undirected weighted graph G(V, E) with 10 vertices and 45 edge, assume (u, v) are two vertices weight of a edge is =4lu- vl then the minimum cost of the...