A directed graph has edges with a specified direction, while an undirected graph has edges that can be followed in either direction. The distinction affects how edges, vertex degrees, routes, and connectivity are interpreted.
This is IB Mathematics: Applications and Interpretation HL content from AHL 3.14: Graph theory.
How the Two Graphs Work
A graph consists of vertices connected by edges. In an undirected graph, an edge joining vertices and represents a two-way connection, so travelling from to is equivalent to travelling from to .
In a directed graph, each edge is an arrow. The directed edge ((A,B)) permits movement from to , but it does not automatically permit movement from to . A separate arrow ((B,A)) would be required.
| Feature | Undirected graph | Directed graph |
|---|---|---|
| Edge representation | Line without arrows | Arrow showing direction |
| Relationship | Two-way | One-way unless both arrows exist |
| Edge notation | Ordered pair ((A,B)) | |
| Vertex measure | Degree: number of incident edges | In-degree and out-degree |
| Example | Two-way roads | One-way roads or social-media follows |
| Connectivity | Connected if every pair of vertices has a path | Strongly connected if every vertex can reach every other vertex following directions |
For example, if has two arrows entering and three leaving, its in-degree is and its out-degree is . These are recorded separately rather than combined as an ordinary degree.
A common misconception is that an arrow between two vertices allows travel both ways. It does not: direction must always be followed.
Exam Technique
In an IB response, first identify whether arrows are present. When analysing a directed graph, state both in-degree and out-degree where relevant, and check paths by following arrow directions. Do not claim that a directed graph is strongly connected merely because all vertices appear linked on the page.