Trees

Videos

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

Reading

DMOI 4.3

Warmup

Problem 1

Prove that every tree is bipartite.

Hint: Recall that a bipartite graph can be split into two sets of nodes \(V_1\) and \(V_2\) with the property that every edge in the graph connects a node from \(V_1\) to a node in \(V_2\) (and there are no edges from nodes in \(V_1\) to nodes in \(V_1\) or from nodes in \(V_2\) to nodes in \(V_2\)).
Hint: Suppose the two sets into which we split nodes are blue and orange. Pick a root vertex and color it blue. What color should the neighbors of this node be? What about their neighbors?

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.