edited by
20,423 views
71 votes
71 votes

Let $G$ be a weighted undirected graph and e be an edge with maximum weight in $G$. Suppose there is a minimum weight spanning tree in $G$ containing the edge $e$. Which of the following statements is always TRUE?

  1. There exists a cutset in $G$ having all edges of maximum weight.
  2. There exists a cycle in $G$ having all edges of maximum weight.
  3. Edge $e$ cannot be contained in a cycle.
  4. All edges in $G$ have the same weight.
edited by

9 Answers

–4 votes
–4 votes
3 will be always true. There is no cycle in a minimum spanning tree ever.
Answer:

Related questions

25 votes
25 votes
3 answers
4
Ishrat Jahan asked Nov 3, 2014
8,917 views
What is the output printed by the following program?#include <stdio.h int f(int n, int k) { if (n == 0) return 0; else if (n % 2) return f(n/2, 2*k) + k; else return f(n/...