Graphs and Trees

Modeling Connections

A graph is a set of vertices (nodes) joined by edges — a mathematical model of connections, from road maps to social networks to program control flow. Graphs are one of the most useful structures in all of computing, and this discrete-math view is exactly what the data-structures unit implements.

Core terminology:

• The degree of a vertex is its number of incident edges.
• A path is a sequence of vertices connected by edges; a cycle is a path returning to its start.
• A graph is connected if there is a path between every pair of vertices.
• Edges may be directed (one-way, a digraph) or undirected (two-way), and may carry weights (costs).

A beautiful early result is the handshaking lemma: the sum of all vertex degrees equals twice the number of edges, $\sum \deg(v) = 2|E|$, because every edge contributes to exactly two vertices' degrees. An immediate corollary: the number of odd-degree vertices is always even.

A tree is a special graph: connected and acyclic (no cycles). Trees have elegant properties — a tree with $n$ vertices has exactly $n - 1$ edges, and there is a unique path between any two vertices. Rooted trees (with a designated root) model hierarchies and are the backbone of the data-structures unit (binary trees, heaps, tries). The whole discrete-math toolkit — sets, relations, induction, counting — comes together in graph theory, which is why it closes the unit.

Common pitfall: miscounting with the handshaking lemma, or forgetting a tree's defining constraints. The sum of degrees is $2|E|$, twice the edge count, not the edge count itself — every edge is counted at both its endpoints. And a tree must be both connected and acyclic; a graph that is acyclic but disconnected is a forest, not a single tree, and a tree on $n$ vertices always has exactly $n-1$ edges (no more, no fewer).