Kruskal runs on a connected undirected graph with 6 vertices. How many edges does the finished spanning tree have?

Answer: ______________

A connected undirected input graph has vertices A, B, C, D and edges AB, BC, CA, CD. A proposed spanning tree keeps only AB, BC and CA. Why is the proposal not a spanning tree?

• It keeps three edges; every four-vertex tree must keep four.
• It uses an edge absent from the original input graph.
• D is isolated, and A, B, C form a cycle.
• It connects all four vertices but has too few edges.

Find the minimum total weight of a spanning tree of this connected undirected graph. Vertices: A, B, C, D, E. Edges: AB 2, BC 3, AC 4, CD 5, DE 6, CE 8, AD 10, BE 12.

Answer: ______________

Kruskal scans this connected undirected graph: vertices A, B, C, D; weights AB 1, CD 2, AC 3, BC 4, BD 5. After accepting AB, CD and AC, why is BC rejected?

• BC closes the cycle B to A to C to B in the selected edges.
• BC must be skipped because it has the greatest weight of all five edges.
• BC joins two separate components, which Kruskal always refuses to merge.

A connected undirected graph has 7 vertices and 9 edges. Edges are deleted to leave a spanning tree, without losing connectivity. How many edges are deleted?

Answer: ______________

Kruskal's accepted forest F is contained in some MST. No edge of F crosses a particular cut. E has minimum weight among edges crossing that cut. What makes E safe to add?

• E is the globally lightest edge, because every edge of the graph crosses this cut.
• Any lightest crossing edge can be added safely to any earlier set of chosen edges.
• Some minimum spanning tree contains every edge of F together with E.

Parent pointers are H to G, G to root F, and J to G. Only find(H) is called, using full path compression. Which pointers remain afterward?

• H to F, G to F, J to F; F stays root.
• H to G, G to H, J to G; H becomes root.
• H to F, G to J, J to F; F stays root.
• H to F, G to F, J to G; F stays root.

find(E) follows E to D to B to root A. With full path compression, which parent pointers change?

• A becomes a child of E, so the representative changes.
• D and E point to A; B already points to A.
• B loses its parent link, so E moves into a separate set.

Kruskal has accepted AB and BC. Union-find has root B for {A,B,C}, while D is a singleton root. It now accepts CD. With union by size, which root link should be made?

• Link B under D, because the new edge starts inside the larger component.
• Link D under B, attaching the smaller set's root to the larger set's root.
• Link C under D, leaving B unchanged, because parent links must match graph edges.

A student uses union by size without path compression and claims the standard bound is the same as using both. Which correction states the usual bounds?

• Size alone gives O(1) worst-case finds, so adding compression cannot reduce the cost of later searches.
• Size alone gives O(alpha(n)) worst-case finds; adding compression can split a set into separate components.
• Size alone: O(log n) worst-case find; both: O(alpha(n)) amortised per operation.