Trees

Videos

Introducing Trees (12:58)
Existence of leaves and number of edges (9:26)
Breadth-first search (8:19)

Reading

Warmup

Problem 1

Prove that every tree is bipartite. Although a picture is likely helpful for understanding this problem, your proof is expected by be in paragraph form. You should use careful statements of the definitions of tree and bipartite in your proof, and explain where you use these definitions in your argument.

Problem 2

Explain why the set of edges followed during the breadth-first search algorithm on a connected graph always forms a tree.

Problem 3

A forest is a graph with no cycles.

Part A

Write a simple explanation of why a forest must necessarily be a union of trees (that is, a graph with one or more connected components, each of which is a tree).

Part B

Suppose that \(F\) is a forest which contains component \(k\) trees and \(n\) vertices. Determine the number of edges in \(F\). Check that your answer works for the case where \(F\) is a single tree.

Part C

Prove that any graph \(G\) with \(n\) vertices and \(m\) edges such that \(n - 1 < m\) not a forest.