Graph Reachability: A Small Mathematical Toolkit
This is a demonstration article for ARTIFICER's textbook environments. It uses a single elementary topic—reachability in finite directed graphs—to show definitions, results, proofs, algorithms, examples, conjectures, and exercises. The exposition is illustrative; edit or replace it with your own material.
1. Mathematical language
Write \(G=(V,E)\) for a directed graph, where \(V\) is its vertex set and \(E \subseteq V \times V\) is its edge set. We write \(u \to v\) when \((u,v)\in E\).
A directed path from \(s\) to \(t\) is a finite sequence \(v_0,\ldots,v_k\) where \(v_0=s\), \(v_k=t\), and every consecutive pair is an edge: \((v_{i-1},v_i)\in E\). A path of length zero is permitted, so every vertex reaches itself.
Vertex \(t\) is reachable from \(s\) when a directed path from \(s\) to \(t\) exists. Write \(s \leadsto t\).
For every vertex \(v\), \(v=v\). We use the ordinary equality relation on vertices; this is a foundational convention, not a result requiring graph theory.
Throughout the algorithmic discussion, assume \(V\) and \(E\) are finite, and that an adjacency list can enumerate the outgoing neighbors of any vertex.
2. Basic results
If \(s \leadsto u\) and \(u \leadsto t\), then \(s \leadsto t\).
Choose a path from \(s\) to \(u\) and one from \(u\) to \(t\). Concatenating their vertex sequences at \(u\) gives a directed walk from \(s\) to \(t\). If any vertices repeat, remove the cycles to obtain a directed path. Thus \(s \leadsto t\).
For each \(v\in V\), we have \(v \leadsto v\) by the zero-length path in Definition 1.
Under Assumption 1, breadth-first search (BFS) starting at \(s\) marks exactly the vertices reachable from \(s\).
Soundness: The start vertex is reachable by a zero-length path. Every other marked vertex is discovered from an already marked vertex through an edge, so it is reachable by extending that vertex's path.
Completeness: Suppose a reachable vertex were unmarked when BFS ended. Take a shortest path from \(s\) to that vertex and consider the first unmarked vertex along it. Its predecessor is marked and would have been processed, forcing the next vertex to be marked—a contradiction.
By Assumption 1, each vertex is inserted into the queue at most once, so the search terminates.
For finite graphs, we can decide whether \(s \leadsto t\) by running BFS from \(s\) and checking whether \(t\) is marked. This follows directly from Theorem 1.
If BFS records a parent when it first discovers a vertex, following the parent pointers from a discovered target back to the start reconstructs a directed path.
With a conventional queue, a visited set, and adjacency lists, BFS runs in \(O(|V|+|E|)\) time. Each vertex is enqueued at most once and each outgoing edge is examined at most once.
3. Concrete interpretations
- procedure BFS(G, s)
- visited ← {s}
- Q ← empty queue
- enqueue(Q, s)
- while Q is not empty do
- u ← dequeue(Q)
- for each v in neighbors(G, u) do
- if v ∉ visited then
- visited ← visited ∪ {v}
- enqueue(Q, v)
- return visited
Let \(V=\{a,b,c\}\) and \(E=\{(a,b),(b,c)\}\). By Lemma 1, \(a \leadsto c\). BFS started at \(a\) visits \(a\), then \(b\), then \(c\).
In Example 1, \(a \leadsto b\), but \(b \not\leadsto a\), because no edge points back to \(a\).
The visited set is not merely a record of execution. By Theorem 1, it is exactly the mathematical set of vertices reachable from the starting vertex.
In an undirected graph, each edge can be traversed in either direction, so reachability is symmetric. That conclusion does not carry over to general directed graphs, as Counterexample 1 shows.
A lemma is usually an intermediate result; a theorem is a result worth emphasizing; a corollary follows readily from another result. The labels express an author's presentation of the argument—not a strict hierarchy of truth.
For the usual shortest-path-in-edge-count guarantee of BFS, process the frontier in FIFO order. Replacing FIFO with LIFO can change the exploration order.
4. Questions for the reader
Investigate: If every vertex in a finite directed graph has at least one outgoing edge, must the graph contain a directed cycle? This is a suggested exercise in making and testing a conjecture, not an unsolved research claim.
Start from any vertex and repeatedly follow an outgoing edge. Use the finiteness of \(V\) to argue that some vertex must occur twice.
Because the graph is finite but the constructed walk continues indefinitely, some vertex must eventually repeat (pigeonhole principle). The segment between two occurrences of that vertex contains a directed cycle. Thus the conjecture is true.
Suppose new edges are added while queries arrive. Design a system for maintaining reachability efficiently without running a complete BFS after every update.
Which trade-offs between update cost, memory, and query latency matter most for a dynamic graph? This is open-ended study material, not a claim that the general subject is mathematically unresolved.
5. How to author these environments
Use standard Obsidian-style Markdown blockquotes. The optional identifier enables links such as Theorem 1 elsewhere on the same page. Numbering is automatic and maintained separately for each environment type.
> [!theorem] A descriptive title {#thm-example}
> Write the statement here. Use $x^2$ for inline math.
>
> Continue in a second paragraph if needed.
> [!proof] Proof of [@thm-example]
> Give an argument here.Other supported kinds include Definition, Notation, Axiom, Assumption, Lemma, Proposition, Theorem, Corollary, Claim, Fact, Algorithm, Example, Counterexample, Observation, Remark, Note, Condition, Conjecture, Exercise, Solution, Problem, Open Problem, and Proof. Ordinary Markdown, internal links and LaTeX math continue to work inside each block.