Motivation
A graph separates the pattern of connections from how it happens to be drawn. Trees isolate the minimum connections needed to join every vertex, while breadth-first search organizes a general graph by distance from a source. Both topics illustrate a central discrete method: prove a global property using a local invariant.
Definitions
Definition 5.1.1
(Graphs, paths, cycles and trees)
A finite simple undirected graph has a finite vertex set and edges that are unordered pairs of distinct vertices, with no repeated edges. A path has distinct vertices and consecutive vertices joined by edges; its length is its number of edges. A cycle has at least three distinct vertices, with consecutive edges and an edge returning to the start. A graph is connected when any two vertices have a path between them. A tree is a connected graph with no cycle; a forest has no cycle. The degree of a vertex is its number of incident edges.
We allow the one-vertex graph as a tree. Throughout the tree theorem . Counting each edge once at each endpoint gives the handshaking identity . In particular, the number of odd-degree vertices is even, since reducing the identity modulo counts precisely those vertices.
Theorem/Proposition
Theorem 5.1.2
(Equivalent descriptions of a tree)
For a finite simple graph with vertices, the following are equivalent: it is a tree; it has exactly one path between each pair of distinct vertices; it is connected and has edges; it is acyclic and has edges.
Theorem 5.1.3
(Breadth-first search finds unweighted distances)
In a finite graph represented by adjacency lists, start at , assign , and put in a first-in, first-out queue. Repeatedly remove the front vertex ; for each undiscovered neighbor , set , record parent , and append . Exactly the vertices reachable from are discovered, and each label is the length of a shortest path from . The running time is when initializing all vertex records.
Proof sketch or proof idea
Proof
(Unique paths, leaves and the forest edge count)
In a connected acyclic graph, two different paths between the same endpoints would contain a cycle, so the path is unique. Conversely, a cycle supplies two distinct paths between two of its vertices; unique paths therefore imply acyclicity and connectivity.
A tree with at least two vertices has a leaf, a vertex of degree one. Take a longest path: an extra neighbor at an endpoint either extends the path or creates a cycle. Removing that leaf leaves a tree. Induction from one vertex gives exactly edges. Every finite connected graph has a spanning tree: while there is a cycle, delete one edge of it, preserving connectivity; the process stops with a tree. Therefore a connected graph with edges already equals its spanning tree. Finally, in a forest with connected components, apply the tree edge count in each component to obtain . If , then , completing the equivalences.
Proof
(Actual parent paths and the queue invariant)
For BFS, every discovered label comes with an actual source path through parent edges, so it cannot be smaller than the shortest distance. Queue labels are nondecreasing: while processing label , newly appended labels are , behind any already queued vertices of labels or . This invariant holds initially and is preserved by each removal and append.
Now consider a shortest path . Inductively is discovered with label . When it is processed, is either newly assigned label or already has label at most , by the queue invariant. Since a prefix of a shortest path is shortest, its distance is ; the actual-path bound forces equality. Thus every reachable vertex is discovered with its true distance. Unreachable vertices cannot acquire parent paths. Each vertex enters the queue once and every undirected edge is scanned twice, establishing the complexity bound.
Proof X-ray
Two inequalities, two different reasons
The proof compares each label with the true distance from both sides, and the two directions rest on different facts. The bound needs only that every label is created by extending a parent's path by one edge; it holds for any discovery order, a stack included. The reverse bound is where first-in, first-out matters. Because the labels in the queue are nondecreasing and each new label is one more than the label being processed, a vertex that is already discovered when is processed was discovered from a vertex of label at most , so its label is at most .
The induction runs along one fixed shortest path, and the fact that a prefix of a shortest path is shortest is what lets the hypothesis at be the distance . Reachability and the time bound come from the same bookkeeping: only reachable vertices acquire parent paths, and each vertex enters the queue once, so each adjacency list is scanned once.
Worked examples
Worked example 5.1.4
(A degree count detects an impossibility)
A finite graph cannot have exactly three odd-degree vertices, regardless of its drawing. Their three odd contributions would make the degree sum odd, contradicting the handshaking identity. The condition is necessary, not sufficient to realize an arbitrary degree list: on four vertices, degrees are impossible because a simple graph has maximum degree .
Worked example 5.1.5
(Edge count alone does not establish a tree)
A triangle together with an isolated vertex has and , but is disconnected and contains a cycle. Thus either connectivity or acyclicity must accompany the count. Removing one triangle edge leaves a forest with two components and two edges, agreeing with .
Worked example 5.1.6
(Tracing BFS and its parent choices)
Take edges . Starting at and scanning before , BFS labels by , by , and by . The recorded parent of is . Scanning first could give parent , but the distances remain the same. The parent edges form a tree on the reachable vertices, even though the original graph has a cycle .
Every edge of a tree is structurally necessary
Remove one edge from a tree. Its endpoints can no longer be connected: an alternative path between them, together with the removed edge, would have formed a cycle in the original tree. The deletion therefore disconnects the graph. It creates exactly two components, since any original path can be cut at that one edge into portions on its two sides. Such an edge is called a bridge.
Conversely, an edge on a cycle is not a bridge. The rest of that cycle still joins its endpoints after deletion, and any path that used the edge can be rerouted along the remaining cycle. Thus in a connected graph, the presence of a cycle identifies an edge that can be removed without losing connectivity. This is the local reason that deleting cycle edges eventually produces a spanning tree.
Adding an edge between two nonadjacent vertices of a tree creates exactly one cycle. The original tree has one path between the endpoints; the new edge closes that path. Any cycle in the enlarged graph must use the new edge because the old graph was acyclic, and removing it leaves the unique original path. This gives both existence and uniqueness of the new cycle. The result is useful when reasoning about incremental network construction, without relying on any visual drawing.
A search forest covers disconnected graphs
BFS from one source has no reason to discover vertices in other connected components. To explore the whole graph, start a new search at an undiscovered vertex after the current queue becomes empty. Repeat until every vertex has been discovered. Each search creates one parent tree for one component; together those parent edges form a spanning forest.
The component count is therefore also the number of search roots. A vertex with no incident edges becomes a one-vertex parent tree and must still be included in that count. Initializing records for every vertex is why the stated time bound contains the vertex term even when the graph has very few edges. A graph with many isolated vertices still requires work to identify them all.
The adjacency-list assumption explains the edge term. Each vertex's neighbors can be scanned in time proportional to its degree, and summing degrees gives twice the number of edges. With an adjacency matrix, looking for neighbors may require scanning an entire row even when the degree is small. A straightforward matrix implementation therefore takes quadratic time in the number of vertices. The mathematical distance theorem survives, but the computational bound depends on the representation.
A short certificate for shortest distances
The output of a search can be verified without replaying the queue. On the reached vertices, check that the source has label zero; every other vertex has a parent of label one less; parent links reach the source; and every edge between reached vertices changes the label by at most one. Also check that no edge leaves the claimed reached set. The parent links provide actual paths of the recorded lengths, while the edge condition supplies a lower bound for any competing path.
Proof
(Parent paths from above, edge inequalities from below)
To see the lower bound, follow any path from the source. At the first vertex the label is zero, and each edge can increase it by at most one. After a given number of edges, the endpoint label is therefore no larger than that number. Thus every source path is at least as long as its endpoint's label. The parent path attains that bound, so the label is exactly the shortest distance. Checking that no edge leaves the reached set ensures omitted vertices really are unreachable.
Proof X-ray
Shortest paths need an upper and a lower bound
Each of the local checks has its own job. The parent conditions (label one less, links reaching the source) build, for every reached vertex, an actual path whose length equals its label: that is the upper bound. The edge condition says the label changes by at most one along each edge, so along any path from the source the endpoint label is at most the number of edges used: that is the lower bound, and it constrains every competing path, not just those in the parent tree. The source label zero anchors both bounds.
The closure check, that no edge leaves the reached set, is what lets the lower bound speak about all source paths: without it, a path could step outside the labeled set, where the edge condition says nothing, and an omitted vertex might in fact be reachable. A plausible parent tree alone proves reachability, but it does not certify shortest paths.
Distance layers and bipartite graphs
A graph is bipartite when its vertices can be split into two sets so that every edge joins different sets. In a connected component, BFS suggests a candidate split: put even-distance vertices on one side and odd-distance vertices on the other. If every edge crosses the split, this is a valid bipartition. If an edge joins vertices of the same distance parity, no bipartition is possible for that component.
Proof
(Parity is forced along every path)
For the impossibility claim, suppose a bipartition existed. Along any path, membership alternates at each edge. Starting from the source, every path of even length must end on its side and every odd-length path on the opposite side. In particular, the parity of each BFS shortest distance would determine its side. An edge joining equal parities would then join vertices on the same side, contradicting the bipartition definition. This proves the test without needing to assume a drawing or a particular parent choice.
For disconnected graphs, perform the test in every component; the two sides can be swapped separately within each component. A triangle fails because the two neighbors of a source have equal odd distance and are adjacent. A four-cycle passes because its alternating layers give a valid split. The examples also show why a graph's having an even number of vertices is not itself a bipartiteness condition.
Concept lensStructural
Distance labels organize several questions
The same BFS layers answer shortest-distance questions, supply parent paths, and propose a two-coloring by parity. These are related uses of one labeled structure, but each conclusion needs its own check. Distance correctness comes from the queue invariant; bipartiteness additionally requires every edge to respect parity.
Common mistakes
Common mistake
(A crossing in a drawing is not a vertex)
An edge crossing in a drawing does not create a vertex unless it is declared one. Also distinguish shortest paths from paths with fewest turns or visually shortest curves: here every edge has length one.
Common mistake
(Replacing the queue by a stack)
The FIFO queue is essential. Replacing it with a stack gives depth-first search, which can discover a vertex first along a longer path.
Common mistake
(Using BFS on weighted graphs)
Weighted graphs require a different distance argument: one heavy edge can be worse than several light ones. With weights and , BFS labels by through the direct edge, although the cheapest route costs . BFS's theorem assumes all edge costs are equal.
Summary
A tree has a unique path between vertices and exactly one fewer edge than vertices. Those counts require structural hypotheses. BFS preserves a queue-layer invariant that makes first discovery give the shortest unweighted distance; parent choices can vary while distances remain fixed.
Exercises
Quick check
(Prove that a forest with ten vertices and three connected components has seven edges.)
Include isolated vertices as one-vertex components.
Solution · Answer
Let component sizes be with sum . Each component is a tree, so it has edges, including when . Adding gives edges. No edges join distinct components, so all edges have been counted.
Quick check
(Give a graph where depth-first discovery can record a nonshortest source path, and show the different BFS distance.)
Specify the neighbor order so the search is unambiguous.
Solution · Answer
Use edges . Let depth-first search recursively explore before from , then from , then from . It first discovers through a path of length , although edge gives distance . BFS discovers both when processing , hence assigns .
Quick check
(Run BFS from on the graph with edges , scanning neighbors in alphabetical order. Record the labels and parents, and apply the parity test for bipartiteness.)
Check every edge, not only the parent edges.
Solution · Answer
Processing discovers and with label and parent . Processing discovers with label and parent ; is already discovered. Processing discovers with label and parent ; is already discovered. The labels are , and . The parent edges all join opposite parities, but the edge joins two vertices of label . The graph is therefore not bipartite; indeed is a triangle, an odd cycle.