Trees & BFS

Trees are the simplest connected graphs — connected with no cycles. We prove their key properties, introduce spanning trees, and learn Breadth-First Search (BFS) as a systematic way to explore graphs and find shortest paths in unweighted graphs.

Learning Objectives

Characterize trees using multiple equivalent definitions

Prove that every tree on n vertices has exactly n-1 edges

Implement and trace BFS on a graph

Use BFS to find shortest paths and connected components

Key Concepts

Trees

A tree is a connected acyclic graph. The following four conditions are equivalent (proof: $1 \Rightarrow 2 \Rightarrow 3 \Rightarrow 4 \Rightarrow 1$ ):

- $G$ is a tree (connected and acyclic)
-For every $u, v$ , there is a unique $u$ - $v$ path
- $G$ is maximally acyclic (adding any edge creates a cycle)
- $G$ is minimally connected (removing any edge disconnects)

A forest is an acyclic graph (a disjoint union of trees). A leaf is a vertex of degree 1.

-
Every tree on $n \geq 2$ vertices has at least 2 leaves
-
A tree on $n$ vertices has exactly $n-1$ edges
-
Adding any edge to a tree creates exactly one cycle
-
A forest with $n$ vertices and $k$ components has $n-k$ edges

Breadth-First Search (BFS)

BFS explores a graph level by level starting from a source vertex $s$ . It uses a queue: visit $s$ , then all neighbors of $s$ , then all unvisited neighbors of those, etc.

BFS computes the shortest path (fewest edges) from $s$ to every reachable vertex. The BFS tree is a spanning tree of the component containing $s$ .

-
BFS runs in $O(n + m)$ time where $n = |V|, m = |E|$
-
BFS gives shortest paths in unweighted graphs
-
Non-tree edges in BFS connect vertices in the same or adjacent levels
-
BFS can detect bipartiteness: a graph is bipartite iff BFS finds no edge within a level

W2: Graphs, Isomorphism & Connectivity W4: Euler Circuits & Hamilton Cycles