Suppose a connected weighted graph G has a unique edge e of minimum weight among all edges in G. Which statement is TRUE?
By the Cut Property / Minimum Weight Edge property, the edge with the absolute smallest weight in the graph must be included in every MST.
If we add a constant positive value c to the weight of EVERY edge in a connected weighted graph G, how does the Minimum Spanning Tree (MST) change?
Adding a constant c to all edges preserves the relative weight order of all spanning trees. Each spanning tree cost increases by exactly (V - 1) * c, leaving the optimal tree structure unchanged.
If we SQUARE the weight of EVERY edge in a connected weighted graph G with all positive edge weights ($w_{i}$ > 1), what happens to its MST?
Since $w_{i}$ > 0 and the squaring function $f(x) = x^2$ is strictly monotonically increasing for x > 0, relative edge weight ordering is preserved, so the set of MST edges remains identical.
Why can Dijkstra's algorithm fail on a weighted directed graph containing edges with NEGATIVE weights?
Dijkstra assumes distance estimates non-decrease along paths (greedy property). Negative edge weights violate this assumption, allowing a closed/visited vertex distance to be updated via a longer path.
What is the time complexity of Dijkstra's algorithm implemented with a Min-Heap priority queue on a graph with V vertices and E edges?
V Extract-Min operations take O(V log V) and E Decrease-Key operations take O(E log V), yielding O((V + E) log V).