Graph Theory Cheat Sheet

Updated 2026-04-27

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.

Table 1: Core Terminology and DefinitionsTable 2: Graph Types and VariantsTable 3: Graph RepresentationsTable 4: Graph Traversal AlgorithmsTable 5: Shortest Path AlgorithmsTable 6: Minimum Spanning Tree AlgorithmsTable 7: Network Flow AlgorithmsTable 8: Connectivity and ComponentsTable 9: Topological Sorting and DAGsTable 10: Graph ColoringTable 11: Matching AlgorithmsTable 12: Special Paths and CyclesTable 13: Graph Metrics and PropertiesTable 14: Centrality MeasuresTable 15: Advanced Graph ProblemsTable 16: Cycle Detection AlgorithmsTable 17: Community Detection and ClusteringTable 18: Graph ApplicationsTable 19: Graph Network ModelsTable 20: Graph Neural Networks and Embeddings

Table 1: Core Terminology and Definitions

Term	Example	Description
Vertex (Node)	`V = {A, B, C, D}`	• Fundamental unit representing an entity in the graph • the terms vertex and node are used interchangeably.
Edge (Arc)	`E = {(A,B), (B,C)}`	• Connection between two vertices • called arc in directed graphs where order matters.
Directed Graph (Digraph)	`A B C`	• Graph where edges have direction • edge (u,v) does not imply edge (v,u) exists.
Undirected Graph	`A B C`	• Graph where edges are bidirectional • connection between u and v works both ways.
Weighted Graph	`A --5-- B --3-- C`	Graph where edges have numerical weights (costs, distances, capacities).
Degree	`deg(v) = 3`	• Number of edges incident to a vertex • in directed graphs: in-degree (incoming) and out-degree (outgoing).
Path	`A B C D`	Sequence of vertices where each adjacent pair is connected by an edge and no vertices repeat.

Table 1: Core Terminology and Definitions

Term	Example	Description
Vertex (Node)	`V = {A, B, C, D}`	• Fundamental unit representing an entity in the graph • the terms vertex and node are used interchangeably.
Edge (Arc)	`E = {(A,B), (B,C)}`	• Connection between two vertices • called arc in directed graphs where order matters.
Directed Graph (Digraph)	`A B C`	• Graph where edges have direction • edge (u,v) does not imply edge (v,u) exists.
Undirected Graph	`A B C`	• Graph where edges are bidirectional • connection between u and v works both ways.
Weighted Graph	`A --5-- B --3-- C`	Graph where edges have numerical weights (costs, distances, capacities).
Degree	`deg(v) = 3`	• Number of edges incident to a vertex • in directed graphs: in-degree (incoming) and out-degree (outgoing).
Path	`A B C D`	Sequence of vertices where each adjacent pair is connected by an edge and no vertices repeat.