Homework: Homework 7. Trees

Assigned

• March 31, 2026

Due

• April 3, 2026 10:00pm

Collaboration

You must work individually this assignment. Make sure you review and understand the policies on the syllabus before you discuss your work on this assignment with anyone.

Submitting

You will submit your compiled pdf on Gradescope. Everything must be typed in \(\Latex\)

Problem 1:

Given a tree with n vertices. How many edges does it have? Prove it.

Problem 2:

Given a connected graph with n vertices. What is the minimum number of edges that it can contain? What is the relationship to Problem 1?

Problem 3:

Prove that every connected graph has a spanning tree.

Problem 4:

Prove that every connected graph has at least one minimum spanning tree.