Trees and Spanning Trees Questions and Answers

Answer: A

The answer is P only.

P is true. Every spanning tree has exactly \(|V| - 1\) edges, so adding the same constant to every edge raises every tree's total by the same amount. The order of trees by weight is unchanged, and so is the minimum spanning tree. (Kruskal's algorithm also sees the same order of edges.)

Q is false. Paths have different numbers of edges, so the increase depends on path length. For example, a direct edge of weight 6 against a two-edge path of weights 2 + 3: before, the two-edge path (5) is shorter; after adding 2 to each edge, it costs 9 while the direct edge costs 8. Paths with more edges are penalized more.

Answer: B

Only statement II is true, so the answer is II only.

II is true (the cycle property): if \(e\) is the heaviest edge on some cycle, then in any spanning tree containing \(e\), removing \(e\) and adding another edge of that cycle reconnects the tree with smaller total weight. So no MST contains \(e\).

I is false. Being the lightest edge of some cycle does not force an edge into the MST. Take vertices A, B, C, D with edges AC = 1, BC = 2, AB = 3, AD = 4 and BD = 5. AB is the lightest edge of the cycle A-B-D (3, 4, 5), yet it is the heaviest edge of the triangle A-B-C, so by the cycle property no MST contains it; the MST is AC, BC, AD. So only II holds.

Answer: B

For all graphs, \(d_{1}(u, v) \le d_{2}(u, v)\).

The minimum spanning tree T is a subgraph of G, so the unique path between u and v in T is also a path in G. The shortest path in G can only be as short as that path or shorter, so \(d_{1} \le d_{2}\).

Equality need not hold, because an MST minimises total weight, not individual distances. In a triangle with edges u-v of weight 3 and u-w, w-v of weight 2 each, the MST keeps the two edges of weight 2, so \(d_{2}(u, v) = 4\) while \(d_{1}(u, v) = 3\). That example rules out '=' and '\(\ge\)', and the case where u and v are joined by an MST edge rules out '\(\ne\)'.

Answer: D

The true statement is In each cycle \(C\) in \(G\), either all edges in \(C\) have even weight OR all edges in \(C\) have odd weight.

Suppose a cycle had an even edge e and an odd edge f. Take a spanning tree that contains e but not f (start from the cycle minus f and extend it). Removing e splits the tree into two parts, and f, lying on the same cycle, reconnects them, so swapping e for f gives another spanning tree whose weight differs by an odd amount. Both trees cannot be even, a contradiction. So the edges of every cycle share one parity.

The other statements fail on examples. A path of two edges of weight 1 has only one spanning tree, of weight 2, so edges need not be even, and a cycle of odd edges does the same. A triangle of odd edges with a pendant edge of weight 2 has every spanning tree of even weight, yet its edges are neither all even nor all odd.

Answer: C

Every MST remains an MST, and SPs need not remain SPs.

Every spanning tree of a graph with n vertices has exactly n - 1 edges. Adding α to every edge raises the weight of every spanning tree by the same amount, (n - 1)α, so their order by weight is unchanged and the minimum ones stay minimum.

Paths are different: a path with k edges gains kα, so paths with more edges are penalised more. Example: a direct edge u-v of weight 3 against a two-edge path u-w-v of weights 1 and 1. Before the update the two-edge path (2) is shorter; after adding α = 2 it costs 6 while the direct edge costs 5. So a shortest path need not stay shortest, which rules out the two options claiming that every SP survives, and the MST argument rules out the other.

Answer: C

The lowest possible Jaccard coefficient is 0.

The coefficient is |T₁ ∩ T₂| / |T₁ ∪ T₂|, so it is 0 exactly when two spanning trees share no edge. K_n has n(n-1)/2 edges and a spanning tree uses n - 1, so there are more than enough edges for two disjoint trees once n ≥ 4.

A concrete pair for n > 4, with vertices 1 to n: the path 1-2-3-...-n, and the path that visits the odd vertices in increasing order and then the even ones (1-3-5-...-2-4-6-...). Every edge of the second path joins two numbers that differ by at least 2, while every edge of the first joins consecutive numbers, so the two spanning trees share no edge and their Jaccard coefficient is 0.

The other values assume two trees must share an edge: 1/(2n-3) is the value when they share exactly one edge (union 2(n-1) - 1 = 2n - 3), and 1/n and 1/(n-1) are not minimal.