# CSCI 2300 Lab 4

CSCI 2300 — Introduction to Algorithms

Lab 4 (document version 1.0) — DUE July 15, 2020
Minimum Spanning Trees and Perfect Matchings
• This lab is to be completed individually. Do not share your work or code with anyone else.
• For all labs, please avoid using Google to find suggestions or solutions. The goal is to use
your own brain to work these problems out, which will help you develop the skills to do well
on the exams and, more importantly, become a substantially better computer scientist.
In this lab, we focus on minimum spanning trees and the new concept of perfect matchings.
1. Show that Prim’s Algorithm works for graphs that contain negative edge weights.
Hint: Start by working out a few examples, then prove the claim by showing that each step
of Prim’s Algorithm works for an edge of negative edge weight.
2. Prove by contradiction that if graph G = (V, E) has a cycle that includes unique heaviest
(highest-weighted) edge e, then e cannot be part of any minimum spanning tree of G.
3. Given undirected tree T = (V, E), write a linear-time algorithm that determines whether T
contains a perfect matching. Here, we define a perfect matching as subset Em of edge set E
that contains edges incident with each vertex exactly once. As an example, in the graph
shown below (not a tree!), we have two perfect matchings, i.e., Em = {{A, B}, {C, D}}
and Em = {{A, C}, {B, D}}.
Be sure to describe the runtime of your algorithm using Big-O() notation.
Hint: Start by looking for specific properties that must be true to have a perfect matching
in a tree (e.g., how many vertices must you have to actually have a perfect matching, how
many perfect matchings can a tree have, etc.?), then generalize into a linear-time algorithm.
What to submit