Graphs, connectivity, and constructive proofs

Prerequisites: Sets, relations, induction, and basic lists.

Learning objectives

• Distinguish paths, reachability, and connected components.
• Prove basic properties of trees.
• Describe a checkable reachability certificate.

A graph states which connections exist

A finite undirected graph consists of a vertex set V and an edge set E containing unordered pairs of vertices. Here assume a simple graph: no loops and no duplicate edges. A path visits vertices with an edge between each consecutive pair. Reachability means some path exists, not that a direct edge exists. In a directed graph, following an edge backward is not allowed unless a reverse edge also exists.

Consider vertices {A,B,C,D,E} and edges {AB,BC,CA,CD}. Vertices A through D form one connected component; E is isolated. A breadth-first traversal starting at A can record parent(B)=A, parent(C)=A, and parent(D)=C. These parent pointers are a certificate that each discovered vertex is reachable. Following D's parents backward reconstructs the path A,C,D.

A certificate should be checkable without simply trusting the traversal. Verify that the root exists, every non-root parent link is a real edge, and repeated parent links reach the root without a cycle. This establishes reachability for listed vertices. To show the list includes the entire component, also show that no edge leaves the listed set for an unlisted vertex. Positive and completeness claims require different evidence.

Trees make a global promise

A tree is a connected graph with no cycle. Between any two vertices in a tree there is exactly one simple path. Connectivity gives at least one. If two distinct simple paths existed, follow them from their first divergence to their next meeting; their combined segments would form a cycle. This contradiction proves uniqueness.

A tree with n vertices has n-1 edges. One induction removes a leaf from a nontrivial finite tree, leaving a smaller tree, then restores its single incident edge. You must justify that a leaf exists: an endpoint of a longest simple path cannot have another neighbor outside the path, and a neighbor farther along the path would create a cycle. The proof uses both finiteness and acyclicity.

Algorithms produce mathematical objects

A traversal of a connected graph chooses a spanning tree, retaining all vertices but only enough edges to preserve connectivity. The original graph can have many extra edges. Breadth-first search additionally gives minimum edge-count distances in an unweighted graph, while an arbitrary spanning tree does not. Weighted shortest paths need different reasoning. Before reusing a graph theorem, check whether its assumptions include direction, weights, repeated edges, or connectedness. A correct theorem applied to the wrong graph model still gives a wrong system design.

Practice problem

For the graph with vertices {A,B,C,D,E,F} and edges {AB,AC,BD,CD,DE}, list its connected components and construct a spanning tree for the component containing A. Give a parent map rooted at A and the resulting path to E. Explain why adding edge BC to your tree creates exactly one cycle. Then provide a certificate that F is not reachable from A, without assuming a failed search is automatically a proof. State which claims change if edges are directed as their written letter order suggests.

Worked solution

The components are {A,B,C,D,E} and {F}. One spanning tree has AB, AC, BD, DE with parents B:A, C:A, D:B, E:D. It gives path A,B,D,E. Adding BC joins vertices already connected by the unique tree path B,A,C; that path and the new edge form one cycle. The original tree has no other cycle, so this addition creates exactly one. The set containing A has no edge to F, and all listed edges remain inside it, which certifies separation. For directed edges, reachability is directional and connected-component terminology must distinguish weak from strong connectivity. The displayed parent edges still give a directed path from A to E, but an undirected tree theorem cannot automatically justify reverse reachability.

Check your understanding

What extra evidence proves a reached set is the entire undirected component?

• Every reached vertex has a unique display label.
• No edge connects a reached vertex to an unreached vertex.
• The graph has at least one cycle.

Explanation

Parent paths prove members are reachable; closure under adjacent edges rules out an omitted reachable vertex.

Adding an edge between two distinct vertices of a tree creates what?

• Exactly one cycle.
• No cycle if the vertices were far apart.
• Two disconnected components.

Explanation

The original tree supplies exactly one path between the endpoints. The added edge closes that path into one cycle.

Primary reading

• Mathematics for Computer Science: MIT OpenCourseWare

Open the study and save your work →