Let 𝐺
be any undirected graph with positive edge weights, and 𝑇 be a
minimum spanning tree
of 𝐺.
For any two vertices, 𝑢 and 𝑣, let 𝑑1(𝑢,
𝑣)
and 𝑑2(𝑢,
𝑣)
be the shortest
distances between 𝑢 and 𝑣 in 𝐺
and 𝑇,
respectively. Which ONE of the options is CORRECT for all possible 𝐺, 𝑇, 𝑢 and 𝑣?

Question

Let 𝐺
be any undirected graph with positive edge weights, and 𝑇 be a
minimum  spanning tree
of 𝐺.
For any two vertices, 𝑢 and 𝑣, let 𝑑1(𝑢,
𝑣)
and 𝑑2(𝑢,
𝑣)
be the  shortest
distances between 𝑢 and 𝑣 in 𝐺
and 𝑇,
respectively. Which ONE of the options is CORRECT for all possible 𝐺, 𝑇, 𝑢 and 𝑣?

Accepted Answer

𝑑1(𝑢, 𝑣) ≤ 𝑑2(𝑢,
𝑣)

Answer

𝑑1(𝑢, 𝑣) ≥ 𝑑2(𝑢, 𝑣)

Answer

𝑑1(𝑢,
𝑣)
≠ 𝑑2(𝑢,
𝑣)

Answer

𝑑1(𝑢, 𝑣) = 𝑑2(𝑢,
𝑣)

Crowdly

Let 𝐺 be any undirected graph with positive edge weights, and 𝑇 be a minimum ...

Want instant access to all verified answers on moodle.spit.ac.in?