Graph Theory Basics
The problem
Most real systems are things connected to things — dependencies, networks, routes, references, social links. Graph theory gives one formalism for all of them, so a single set of algorithms (reachability, shortest path, cycle detection, ordering) solves problems in every domain at once.
Why now
Relations describe pairwise connection, but questions about the structure of connection — 'is there a path?', 'is there a cycle?', 'what order satisfies all dependencies?' — need vertices-and-edges as first-class objects plus properties proven about them. A relation is one edge set; a graph is the object you can traverse.
Mental model
A graph is dots and lines: vertices are entities, edges are relationships. Directed edges give flow (dependency, causality); undirected edges give symmetry. Nearly every 'hard' graph question reduces to walking: what can I reach, how cheaply, and do I ever come back to where I started (a cycle). A DAG — directed, no cycles — is exactly the shape of any valid dependency system, including this curriculum itself.
Requires
- Sets & LogicMathematical Thinking
A graph is defined as a pair of sets (V, E) with E a set of vertex pairs; every graph property is a proposition quantified over these sets.
- Functions & RelationsMathematical Thinking
An edge set is precisely a relation on V; directed vs. undirected corresponds to whether the relation is symmetric. Without relations, a graph is just a picture.
Helps
- Proof TechniquesMathematical Thinking
The useful graph facts (a tree has n−1 edges, a DAG always admits a topological order) are proved by induction; following those proofs builds real intuition — but you can use the facts without proving them.
Unlocks
Related
Used in
- Package managers and build systems (dependency resolution = topological sort of a DAG)
- Git history (a commit DAG)
- Network routing (shortest path over weighted graphs)
- React's rendering tree and reconciliation
- This project: SEDG itself is a DAG of concepts
Projects
- Model your current project's package dependencies as a graph and detect whether any cycle exists
- Implement topological sort and use it to print a valid learning order for this domain's five topics
Examples
- npm install ordering: packages are vertices, 'depends on' edges — install order is a topological sort
- Deadlock detection: processes and resources as a directed graph; a cycle means deadlock
Resources
Mastery checklist
- I can model a real system as a graph, choosing directed vs. undirected and justifying it
- I can explain why a dependency system must be a DAG and what a cycle would mean
- I can perform a topological sort by hand on a small DAG
- I can recognize when a problem is secretly reachability, shortest path, or cycle detection