Graph theory is the mathematical study of graphs — structures consisting of vertices (nodes) connected by edges (links) — originating in the 18th century with Euler's solution to the Seven Bridges of Königsberg problem. It provides essential foundations for modeling relationships in computer science, social networks, transportation systems, and biological networks. The field's power lies in its ability to represent complex interconnected systems as simple mathematical objects, enabling analysis through traversal algorithms, shortest path computations, and connectivity measures. A key distinction to internalize: edges can be directed (one-way arrows) or undirected (bidirectional connections), and graphs can be weighted (edges have costs) or unweighted — these properties fundamentally change which algorithms apply and what problems can be solved efficiently. In recent years, graph neural networks (GNNs) have extended classical graph theory into machine learning, enabling deep learning directly on graph-structured data for tasks such as node classification, link prediction, and molecular property prediction.
What This Cheat Sheet Covers
This topic spans 20 focused tables and 137 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
Table 1: Core Terminology and Definitions
The vocabulary here is the foundation everything else builds on — vertices and edges, the difference between directed and undirected connections, and the subtle but important distinctions between a walk, a trail, a path, and a cycle (mostly about whether vertices or edges are allowed to repeat). Nail down connectivity and the handshaking lemma early, since later algorithms constantly assume you already speak this language.
| Term | Example | Description |
|---|---|---|
V = {A, B, C, D} | • Fundamental unit representing an entity in the graph • the terms vertex and node are used interchangeably. | |
E = {(A,B), (B,C)} | • Connection between two vertices • called arc in directed graphs where order matters. | |
A B C | • Graph where edges have direction • edge (u,v) does not imply edge (v,u) exists. | |
A B C | • Graph where edges are bidirectional • connection between u and v works both ways. | |
A --5-- B --3-- C | Graph where edges have numerical weights (costs, distances, capacities). | |
deg(v) = 3 | • Number of edges incident to a vertex • in directed graphs: in-degree (incoming) and out-degree (outgoing). | |
A B C D | Sequence of vertices where each adjacent pair is connected by an edge and no vertices repeat. |