Graph Theory: A Complete Summary of Definitions, Theorems, and Proofs

A single-article overview of graph theory, from basic definitions through planarity, coloring, and matroids. Covers all the key definitions, theorems, and algorithms needed for discrete mathematics and competitive programming, organized with a topic dependency diagram.

Folio Official

March 1, 2026

1. Introduction: How to Use This Article

This article provides a single-page panoramic view of undergraduate graph theory. For each topic, we present the key definitions, major theorems, and algorithms in concise form.

How to use this page:

Newcomers: read the sections in order to build a coherent picture of the subject.
Review or exam preparation: jump to any section from the table of contents.
Competitive programming reference: Section 14, “ Theorem and Algorithm Directory,”{} collects all the major results in one list.

The dependency diagram below shows how the main topics are interrelated.

graph TD
    A["Basic Definitions"] --> B["Paths and Connectivity"]
    B --> C["Trees and Forests"]
    B --> D["Eulerian and Hamiltonian Graphs"]
    C --> E["Shortest Paths"]
    B --> E
    B --> F["Directed Graphs and Topological Sorting"]
    B --> G["Matchings and Coverings"]
    G --> H["Network Flow"]
    A --> I["Planar Graphs"]
    I --> J["Graph Coloring"]
    A --> K["Algebraic Graph Theory"]
    C --> L["Matroids and the Greedy Algorithm"]

    style A fill:#f5f5f5,stroke:#333,color:#000
    style E fill:#f5f5f5,stroke:#333,color:#000
    style H fill:#f5f5f5,stroke:#333,color:#000
    style L fill:#f5f5f5,stroke:#333,color:#000

Remark 1.

This article is designed to accompany the “ Graph Theory Textbook”{} series. Links at the end of each section point to the corresponding full-length chapter for detailed exposition and complete proofs.

2. Basic Definitions

Definition 2 (Graph).

An undirected graph

G = (V, E)

consists of a finite set

V

(the vertex set) and a set

E \subseteq (2 V)

of two-element subsets of

V

(the edge set). A directed graph

G = (V, A)

has arcs given by ordered pairs

A \subseteq V \times V

Definition 3 (Degree).

In an undirected graph, the degree

de g (v)

of a vertex

v

is the number of edges incident to

v

. In a directed graph, one distinguishes the in-degree

de g^{-} (v)

and the out-degree

de g^{+} (v)

Theorem 4 (Handshaking lemma).

In an undirected graph

G = (V, E)

v \in V \sum de g (v) = 2∣ E ∣

In particular, the number of vertices of odd degree is always even.

Definition 5 (Special graphs).

Complete graph $K_{n}$ : the graph on $n$ vertices in which every pair of vertices is adjacent. $∣ E ∣ = (2 n)$ .
Complete bipartite graph $K_{m, n}$ : $V = V_{1} \cup V_{2}$ with $∣ V_{1} ∣ = m$ , $∣ V_{2} ∣ = n$ , and every vertex in $V_{1}$ adjacent to every vertex in $V_{2}$ .
Complement $\overset{ˉ}{G}$ : $E (\overset{ˉ}{G}) = (2 V) ∖ E (G)$ .

The complete graph $K_{5}$ and the complete bipartite graph $K_{2, 3}$ :

Definition 6 (Graph isomorphism).

Graphs

G_{1} = (V_{1}, E_{1})

and

G_{2} = (V_{2}, E_{2})

are isomorphic if there exists a bijection

φ : V_{1} \to V_{2}

such that

{u, v} \in E_{1} ⟺ {φ (u), φ (v)} \in E_{2}

For more details:

https://interconnectd.app/articles/frCbKNxQy0LCIv0iVHDZ

3. Paths and Connectivity

Definition 7 (Paths and cycles).

A vertex sequence

v_{0}, v_{1}, \dots, v_{k}

in which each consecutive pair is joined by an edge is called a walk. If no vertex is repeated, it is a path. If

v_{0} = v_{k}

, it is a cycle.

Definition 8 (Connectivity).

A graph

G

is connected if for every pair of vertices

u, v

there exists a path from

u

v

. A maximal connected subgraph is called a connected component.

Definition 9 (Vertex and edge connectivity).

The vertex connectivity

κ (G)

is the minimum number of vertices whose removal disconnects

G

. The edge connectivity

λ (G)

is the minimum number of edges whose removal disconnects

G

Theorem 10 (Whitney's inequality).

κ (G) \leq λ (G) \leq δ (G)

where

δ (G) = min_{v \in V} de g (v)

is the minimum degree.

Definition 11 (Cut vertices and bridges).

A vertex whose removal increases the number of connected components is called a cut vertex. An edge whose removal increases the number of connected components is called a bridge.

Theorem 12 (Bipartiteness criterion).

A graph

G

is bipartite

⟺

G

contains no odd cycle.

Theorem 13 (Menger's theorem).

For two vertices

s

and

t

in a graph

G

, the maximum number of internally vertex-disjoint

s

–

t

paths equals the minimum size of an

s

–

t

separating set.

For more details:

https://interconnectd.app/articles/HIsIycrl4LGkftbzmrIU

4. Trees and Forests

Definition 14 (Tree).

A connected graph with no cycles is called a tree. A graph with no cycles (not necessarily connected) is called a forest.

A tree on $7$ vertices ( $∣ E ∣ = 6 = n - 1$ ):

Theorem 15 (Equivalent characterizations of trees).

For a graph

T

n

vertices, the following are equivalent:

$T$ is a tree (connected and acyclic).
$T$ is connected and has $∣ E ∣ = n - 1$ .
$T$ is acyclic and has $∣ E ∣ = n - 1$ .
There is exactly one path between any two vertices.
$T$ is connected, but removing any edge disconnects it.
$T$ is acyclic, but adding any edge creates a cycle.

Theorem 16 (Cayley's formula).

The number of labeled trees on

n

vertices is

n^{n - 2}

Definition 17 (Spanning tree).

A spanning tree of a graph

G

is a subgraph of

G

that includes every vertex of

G

and is a tree.

Definition 18 (Minimum spanning tree).

In an edge-weighted graph, a spanning tree whose total edge weight is minimized is called a minimum spanning tree (MST).

Key algorithms:

Kruskal's algorithm: sort edges by weight and add each edge that does not create a cycle. $O (∣ E ∣ lo g ∣ E ∣)$ .
Prim's algorithm: grow the tree from a starting vertex by always adding the minimum-weight edge leaving the current tree. $O (∣ E ∣ lo g ∣ V ∣)$ .

Theorem 19 (Cut property).

For any cut (a partition of

V

into two nonempty sets), the minimum-weight edge crossing the cut belongs to some MST.

For more details:

https://interconnectd.app/articles/YzatnhNAeHrFWs5N5rdK

5. Eulerian and Hamiltonian Graphs

Definition 20 (Eulerian circuit and Eulerian graph).

A closed walk that traverses every edge exactly once is called an Eulerian circuit. A graph that admits an Eulerian circuit is called an Eulerian graph.

Theorem 21 (Euler's theorem).

A connected graph

G

is Eulerian

⟺

every vertex of

G

has even degree.

Definition 22 (Hamiltonian cycle).

A cycle that visits every vertex exactly once is called a Hamiltonian cycle.

Theorem 23 (Dirac's theorem).

G

is a simple graph on

n \geq 3

vertices with

δ (G) \geq n /2

, then

G

has a Hamiltonian cycle.

Theorem 24 (Ore's theorem).

G

is a simple graph on

n \geq 3

vertices such that

de g (u) + de g (v) \geq n

for every pair of non-adjacent vertices

u, v

, then

G

has a Hamiltonian cycle.

Remark 25.

Deciding the existence of an Eulerian circuit can be done in

O (∣ E ∣)

time, whereas deciding the existence of a Hamiltonian cycle is NP-complete.

For more details:

https://interconnectd.app/articles/1TJ9SYhKvLV6xsyieLaV

6. Shortest Path Problems

Definition 26 (Shortest path).

In a graph with edge weights

w : E \to R

, the shortest path from

s

t

is a path minimizing the sum of edge weights. We write

dist (s, t)

for this minimum total weight.

Key algorithms:

BFS: single-source shortest paths in unweighted graphs. $O (∣ V ∣ + ∣ E ∣)$ .
Dijkstra: single-source shortest paths with non-negative weights. $O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)$ (binary heap).
Bellman–Ford: single-source shortest paths allowing negative weights. $O (∣ V ∣∣ E ∣)$ . Also detects negative cycles.
Floyd–Warshall: all-pairs shortest paths. $O (∣ V ∣^{3})$ .
DAG shortest paths: relax edges in topological order. $O (∣ V ∣ + ∣ E ∣)$ .

Theorem 27 (Correctness of Dijkstra's algorithm).

In a graph with non-negative edge weights, Dijkstra's algorithm maintains the invariant that the distance label of every finalized vertex equals its true shortest-path distance from the source.

Theorem 28 (Negative cycle detection).

Bellman–Ford detects a negative cycle reachable from the source

s

if and only if an update occurs during the

∣ V ∣

-th iteration.

For more details:

https://interconnectd.app/articles/ffriRQaeeGIg10QEJCU1

7. Directed Graphs and Topological Sorting

Definition 29 (Strong connectivity).

A directed graph

G

is strongly connected if for every pair of vertices

u, v

there exist directed paths from

u

v

and from

v

u

. A maximal strongly connected subgraph is called a strongly connected component (SCC).

Theorem 30 (SCC condensation).

Contracting each SCC of a directed graph to a single vertex yields a DAG (directed acyclic graph).

SCC algorithms:

Kosaraju's algorithm: two passes of DFS. $O (∣ V ∣ + ∣ E ∣)$ .
Tarjan's algorithm: one pass of DFS with a stack. $O (∣ V ∣ + ∣ E ∣)$ .

Definition 31 (Topological sorting).

A topological sort of a DAG

G

is a total ordering

v_{1}, v_{2}, \dots, v_{n}

of its vertices such that

(v_{i}, v_{j}) \in A \Rightarrow i < j

Theorem 32.

A directed graph admits a topological sort

⟺

it is a DAG.

Remark 33.

Dynamic programming on a DAG proceeds in topological order, solving problems such as longest paths and path counting in

O (∣ V ∣ + ∣ E ∣)

time.

For more details:

https://interconnectd.app/articles/nNEOHtN9fe6Uf9vDnOdQ

8. Matchings and Coverings

Definition 34 (Matching).

A set of edges

M \subseteq E

in which no two edges share an endpoint is called a matching. A matching of maximum cardinality is called a maximum matching.

A bipartite graph with a matching (thick edges):

Definition 35 (Augmenting path).

An augmenting path with respect to a matching

M

is a path whose edges alternate between edges not in

M

and edges in

M

, and whose endpoints are both unmatched.

Theorem 36 (Berge's theorem).

A matching

M

is maximum

⟺

there is no augmenting path with respect to

M

Theorem 37 (Hall's marriage theorem).

In a bipartite graph

G = (X \cup Y, E)

, a perfect matching of

X

exists

⟺

∣ N (S) ∣ \geq ∣ S ∣

for every

S \subseteq X

(Hall's condition).

Theorem 38 (König's theorem).

In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

Theorem 39 (Gale–Shapley algorithm).

The stable matching problem (given preference lists for

n

agents on each side, find a matching with no blocking pair) can be solved in

O (n^{2})

time.

For more details:

https://interconnectd.app/articles/TeuUPkNltaVHPIozeFhd

9. Network Flow

Definition 40 (Flow network).

A flow network is a tuple

(G, c, s, t)

consisting of a directed graph

G = (V, A)

, a capacity function

c : A \to R_{\geq 0}

, a source

s

, and a sink

t

. A flow

f : A \to R_{\geq 0}

is a function satisfying the capacity constraint

f (e) \leq c (e)

and the conservation of flow at every vertex other than

s

and

t

Definition 41 (Cut).

For

S \subseteq V

with

s \in S

and

t \in / S

, the capacity of the cut

(S, V ∖ S)

c (S, V ∖ S) = \sum_{(u, v) \in A, u \in S, v \in / S} c (u, v)

Theorem 42 (Max-flow min-cut theorem).

The value of a maximum flow equals the capacity of a minimum cut.

Key algorithms:

Ford–Fulkerson method: iteratively find augmenting paths in the residual graph.
Edmonds–Karp: use BFS to select augmenting paths. $O (∣ V ∣∣ E ∣^{2})$ .
Dinic's algorithm: uses level graphs and blocking flows. $O (∣ V ∣^{2} ∣ E ∣)$ .

Theorem 43 (Reduction to bipartite matching).

The maximum matching in a bipartite graph can be computed by adding a source

s

and a sink

t

, assigning unit capacities, and solving the resulting maximum flow problem.

For more details:

https://interconnectd.app/articles/LvJFQmlPzZAIqGzkpcIv

10. Planar Graphs

Definition 44 (Planar graph).

A graph is planar if it can be drawn in the plane without edge crossings. Such a drawing is called a plane graph.

Theorem 45 (Euler's polyhedron formula).

For a connected plane graph

G

V - E + F = 2

where

V

is the number of vertices,

E

the number of edges, and

F

the number of faces (including the outer face).

Theorem 46 (Upper bound on edges).

In a simple connected planar graph with

∣ V ∣ \geq 3

∣ E ∣ \leq 3∣ V ∣ - 6

. In particular,

K_{5}

is not planar. If

G

is triangle-free (as in the

K_{3, 3}

case), then

∣ E ∣ \leq 2∣ V ∣ - 4

Theorem 47 (Kuratowski's theorem).

A graph

G

is planar

⟺

G

contains no subdivision of

K_{5}

K_{3, 3}

as a subgraph.

Definition 48 (Dual graph).

The dual graph

G^{*}

of a plane graph

G

has a vertex for each face of

G

, and two vertices of

G^{*}

are joined by an edge whenever the corresponding faces of

G

share a boundary edge.

For more details:

https://interconnectd.app/articles/wLP1cCOHrfu571MlDd3V

11. Graph Coloring

Definition 49 (Vertex coloring).

A vertex coloring of a graph

G

is an assignment of colors to vertices such that no two adjacent vertices receive the same color. If

G

can be colored with

k

colors,

G

is said to be

k

-colorable. The minimum such

k

is the chromatic number

χ (G)

Theorem 50 (Basic inequality).

ω (G) \leq χ (G) \leq Δ (G) + 1

where

ω (G)

is the clique number and

Δ (G)

is the maximum degree.

Theorem 51 (Brooks's theorem).

G

is a connected graph that is neither a complete graph nor an odd cycle, then

χ (G) \leq Δ (G)

Definition 52 (Chromatic polynomial).

Let

P (G, k)

denote the number of proper

k

-colorings of

G

. Then

P (G, k)

is a polynomial in

k

Theorem 53 (Vizing's theorem).

For the edge chromatic number (or chromatic index)

χ^{'} (G)

of a simple graph

G

Δ (G) \leq χ^{'} (G) \leq Δ (G) + 1

Theorem 54 (Four color theorem).

Every planar graph is

4

-colorable (

χ (G) \leq 4

Remark 55.

The four color theorem was first proved in 1976 by Appel and Haken using a computer-assisted case analysis.

For more details:

https://interconnectd.app/articles/rTuW1frjXvB379VAnpDK

12. Algebraic Graph Theory

Definition 56 (Adjacency matrix).

The adjacency matrix of a graph

G

n

vertices is the

n \times n

matrix

A = (a_{ij})

where

a_{ij} = 1

{i, j} \in E

and

a_{ij} = 0

otherwise.

Theorem 57 (Counting walks).

The

(i, j)

-entry of

A^{k}

equals the number of walks of length

k

from vertex

i

to vertex

j

Definition 58 (Laplacian matrix).

The Laplacian matrix is

L = D - A

, where

D

is the diagonal degree matrix.

L

is positive semidefinite with eigenvalues

0 \leq λ_{1} \leq λ_{2} \leq \dots \leq λ_{n}

Theorem 59 (Laplacian and connectivity).

The multiplicity of the eigenvalue

0

L

equals the number of connected components of

G

. In particular,

λ_{2} > 0 ⟺ G

is connected. The quantity

λ_{2}

is called the algebraic connectivity.

Theorem 60 (Matrix tree theorem (Kirchhoff)).

The number of spanning trees of

G

equals any cofactor of

L

(i.e., any

(i, i)

-cofactor of the Laplacian matrix).

For more details:

https://interconnectd.app/articles/VaqPp5RARg4xmSCQDDel

13. Matroids and the Greedy Algorithm

Definition 61 (Matroid).

A matroid is a pair

(E, I)

consisting of a finite set

E

and a collection

I \subseteq 2^{E}

of subsets satisfying:

$\emptyset \in I$ .
If $A \in I$ and $B \subseteq A$ , then $B \in I$ (hereditary property).
If $A, B \in I$ and $∣ A ∣ < ∣ B ∣$ , then there exists $b \in B ∖ A$ such that $A \cup {b} \in I$ (exchange property).

The members of

I

are called independent sets.

Example 62 (Graphic matroid).

Given a graph

G = (V, E)

, declare a subset of

E

to be independent if it contains no cycle. The resulting pair

(E, I)

is a matroid called the graphic matroid. Its independent sets are the forests of

G

, and its bases are the spanning trees.

Theorem 63 (Optimality of the greedy algorithm).

(E, I)

is a matroid and

w : E \to R

is a weight function, then the greedy algorithm—adding elements in decreasing order of weight, provided independence is maintained—produces a maximum-weight independent set.

Theorem 64 (Converse).

(E, I)

satisfies the hereditary property, then the greedy algorithm yields a maximum-weight independent set for every weight function

w

if and only if

(E, I)

is a matroid.

Remark 65.

Kruskal's algorithm is nothing other than the greedy algorithm on the graphic matroid. The matroid framework provides the theoretical answer to the question: “ Why does a greedy strategy produce an optimal solution?”

For more details:

https://interconnectd.app/articles/XHUQNbZEzRsQZwUv2NGF

14. Theorem and Algorithm Directory

A one-line summary of the principal theorems and algorithms encountered in graph theory, for quick reference.

Fundamental theorems:

Handshaking lemma: $\sum de g (v) = 2∣ E ∣$ .
Bipartiteness criterion: no odd cycle $⟺$ bipartite.
Edge count of a tree: a tree on $n$ vertices has $n - 1$ edges.
Cayley's formula: the number of labeled trees on $n$ vertices is $n^{n - 2}$ .
Euler's theorem: connected $+$ all vertices of even degree $⟺$ Eulerian circuit.
Dirac's theorem: $δ (G) \geq n /2$ implies a Hamiltonian cycle.
Euler's polyhedron formula: $V - E + F = 2$ .
Kuratowski's theorem: no $K_{5}$ or $K_{3, 3}$ subdivision $⟺$ planar.
Four color theorem: every planar graph is $4$ -colorable.
Brooks's theorem: $χ (G) \leq Δ (G)$ (excluding complete graphs and odd cycles).
Vizing's theorem: $Δ (G) \leq χ^{'} (G) \leq Δ (G) + 1$ .

Matching and flow theorems:

Berge's theorem: maximum matching $⟺$ no augmenting path.
Hall's marriage theorem: $∣ N (S) ∣ \geq ∣ S ∣$ $⟺$ perfect matching exists.
König's theorem: in bipartite graphs, maximum matching $=$ minimum vertex cover.
Max-flow min-cut theorem: maximum flow $=$ minimum cut.
Menger's theorem: maximum number of independent paths $=$ minimum separating set.

Algebraic and structural theorems:

Matrix tree theorem: number of spanning trees $=$ cofactor of the Laplacian.
$A^{k}$ theorem: $(A^{k})_{ij}$ $=$ number of walks of length $k$ .
Greedy optimality: the greedy algorithm is optimal on matroids.

Key algorithms:

BFS / DFS: $O (∣ V ∣ + ∣ E ∣)$
Dijkstra: $O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)$
Bellman–Ford: $O (∣ V ∣∣ E ∣)$
Floyd–Warshall: $O (∣ V ∣^{3})$
Kruskal: $O (∣ E ∣ lo g ∣ E ∣)$
Prim: $O (∣ E ∣ lo g ∣ V ∣)$
Kosaraju / Tarjan (SCC): $O (∣ V ∣ + ∣ E ∣)$
Dinic (max flow): $O (∣ V ∣^{2} ∣ E ∣)$
Gale–Shapley (stable matching): $O (n^{2})$

15. Appendix: Notation and Terminology

Symbol	Name	Meaning
$G = (V, E)$	Graph	A vertex set $V$ paired with an edge set $E$
$de g (v)$	Degree	Number of edges incident to $v$
$δ (G)$	Minimum degree	$min_{v} de g (v)$
$Δ (G)$	Maximum degree	$max_{v} de g (v)$
$κ (G)$	Vertex connectivity	Min. vertices to remove to disconnect $G$
$λ (G)$	Edge connectivity	Min. edges to remove to disconnect $G$
$K_{n}$	Complete graph	The complete graph on $n$ vertices
$K_{m, n}$	Complete bipartite graph	Complete bipartite graph of sizes $m, n$
$χ (G)$	Chromatic number	Min. colors for a proper vertex coloring
$χ^{'} (G)$	Chromatic index	Min. colors for a proper edge coloring
$ω (G)$	Clique number	Size of the largest clique
$A$	Adjacency matrix	$a_{ij} = [{i, j} \in E]$
$L = D - A$	Laplacian	Degree matrix minus adjacency matrix
MST	Minimum spanning tree	Spanning tree of minimum total weight
SCC	Strongly connected component	Maximal strongly connected subgraph
DAG	Directed acyclic graph	Directed graph with no directed cycles
NP-complete	NP-complete	Hardest problems in NP (verifiable in polynomial time)

Graph Theory Discrete Mathematics Summary Theorem Reference Algorithms Competitive Programming

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Graph Theory: A Complete Summary of Definitions, Theorems, and Proofs

Folio Official

March 1, 2026

1. Introduction: How to Use This Article

This article provides a single-page panoramic view of undergraduate graph theory. For each topic, we present the key definitions, major theorems, and algorithms in concise form.

How to use this page:

Newcomers: read the sections in order to build a coherent picture of the subject.
Review or exam preparation: jump to any section from the table of contents.
Competitive programming reference: Section 14, “ Theorem and Algorithm Directory,”{} collects all the major results in one list.

The dependency diagram below shows how the main topics are interrelated.

graph TD
    A["Basic Definitions"] --> B["Paths and Connectivity"]
    B --> C["Trees and Forests"]
    B --> D["Eulerian and Hamiltonian Graphs"]
    C --> E["Shortest Paths"]
    B --> E
    B --> F["Directed Graphs and Topological Sorting"]
    B --> G["Matchings and Coverings"]
    G --> H["Network Flow"]
    A --> I["Planar Graphs"]
    I --> J["Graph Coloring"]
    A --> K["Algebraic Graph Theory"]
    C --> L["Matroids and the Greedy Algorithm"]

    style A fill:#f5f5f5,stroke:#333,color:#000
    style E fill:#f5f5f5,stroke:#333,color:#000
    style H fill:#f5f5f5,stroke:#333,color:#000
    style L fill:#f5f5f5,stroke:#333,color:#000

Remark 1.

2. Basic Definitions

Definition 2 (Graph).

An undirected graph

G = (V, E)

consists of a finite set

V

(the vertex set) and a set

E \subseteq (2 V)

of two-element subsets of

V

(the edge set). A directed graph

G = (V, A)

has arcs given by ordered pairs

A \subseteq V \times V

Definition 3 (Degree).

In an undirected graph, the degree

de g (v)

of a vertex

v

is the number of edges incident to

v

. In a directed graph, one distinguishes the in-degree

de g^{-} (v)

and the out-degree

de g^{+} (v)

Theorem 4 (Handshaking lemma).

In an undirected graph

G = (V, E)

v \in V \sum de g (v) = 2∣ E ∣

In particular, the number of vertices of odd degree is always even.

Definition 5 (Special graphs).

Complete graph $K_{n}$ : the graph on $n$ vertices in which every pair of vertices is adjacent. $∣ E ∣ = (2 n)$ .
Complete bipartite graph $K_{m, n}$ : $V = V_{1} \cup V_{2}$ with $∣ V_{1} ∣ = m$ , $∣ V_{2} ∣ = n$ , and every vertex in $V_{1}$ adjacent to every vertex in $V_{2}$ .
Complement $\overset{ˉ}{G}$ : $E (\overset{ˉ}{G}) = (2 V) ∖ E (G)$ .

The complete graph $K_{5}$ and the complete bipartite graph $K_{2, 3}$ :

Definition 6 (Graph isomorphism).

Graphs

G_{1} = (V_{1}, E_{1})

and

G_{2} = (V_{2}, E_{2})

are isomorphic if there exists a bijection

φ : V_{1} \to V_{2}

such that

{u, v} \in E_{1} ⟺ {φ (u), φ (v)} \in E_{2}

For more details:

https://interconnectd.app/articles/frCbKNxQy0LCIv0iVHDZ

3. Paths and Connectivity

Definition 7 (Paths and cycles).

A vertex sequence

v_{0}, v_{1}, \dots, v_{k}

in which each consecutive pair is joined by an edge is called a walk. If no vertex is repeated, it is a path. If

v_{0} = v_{k}

, it is a cycle.

Definition 8 (Connectivity).

A graph

G

is connected if for every pair of vertices

u, v

there exists a path from

u

v

. A maximal connected subgraph is called a connected component.

Definition 9 (Vertex and edge connectivity).

The vertex connectivity

κ (G)

is the minimum number of vertices whose removal disconnects

G

. The edge connectivity

λ (G)

is the minimum number of edges whose removal disconnects

G

Theorem 10 (Whitney's inequality).

κ (G) \leq λ (G) \leq δ (G)

where

δ (G) = min_{v \in V} de g (v)

is the minimum degree.

Definition 11 (Cut vertices and bridges).

A vertex whose removal increases the number of connected components is called a cut vertex. An edge whose removal increases the number of connected components is called a bridge.

Theorem 12 (Bipartiteness criterion).

A graph

G

is bipartite

⟺

G

contains no odd cycle.

Theorem 13 (Menger's theorem).

For two vertices

s

and

t

in a graph

G

, the maximum number of internally vertex-disjoint

s

–

t

paths equals the minimum size of an

s

–

t

separating set.

For more details:

https://interconnectd.app/articles/HIsIycrl4LGkftbzmrIU

4. Trees and Forests

Definition 14 (Tree).

A connected graph with no cycles is called a tree. A graph with no cycles (not necessarily connected) is called a forest.

A tree on $7$ vertices ( $∣ E ∣ = 6 = n - 1$ ):

Theorem 15 (Equivalent characterizations of trees).

For a graph

T

n

vertices, the following are equivalent:

$T$ is a tree (connected and acyclic).
$T$ is connected and has $∣ E ∣ = n - 1$ .
$T$ is acyclic and has $∣ E ∣ = n - 1$ .
There is exactly one path between any two vertices.
$T$ is connected, but removing any edge disconnects it.
$T$ is acyclic, but adding any edge creates a cycle.

Theorem 16 (Cayley's formula).

The number of labeled trees on

n

vertices is

n^{n - 2}

Definition 17 (Spanning tree).

A spanning tree of a graph

G

is a subgraph of

G

that includes every vertex of

G

and is a tree.

Definition 18 (Minimum spanning tree).

In an edge-weighted graph, a spanning tree whose total edge weight is minimized is called a minimum spanning tree (MST).

Key algorithms:

Kruskal's algorithm: sort edges by weight and add each edge that does not create a cycle. $O (∣ E ∣ lo g ∣ E ∣)$ .
Prim's algorithm: grow the tree from a starting vertex by always adding the minimum-weight edge leaving the current tree. $O (∣ E ∣ lo g ∣ V ∣)$ .

Theorem 19 (Cut property).

For any cut (a partition of

V

into two nonempty sets), the minimum-weight edge crossing the cut belongs to some MST.

For more details:

https://interconnectd.app/articles/YzatnhNAeHrFWs5N5rdK

5. Eulerian and Hamiltonian Graphs

Definition 20 (Eulerian circuit and Eulerian graph).

A closed walk that traverses every edge exactly once is called an Eulerian circuit. A graph that admits an Eulerian circuit is called an Eulerian graph.

Theorem 21 (Euler's theorem).

A connected graph

G

is Eulerian

⟺

every vertex of

G

has even degree.

Definition 22 (Hamiltonian cycle).

A cycle that visits every vertex exactly once is called a Hamiltonian cycle.

Theorem 23 (Dirac's theorem).

G

is a simple graph on

n \geq 3

vertices with

δ (G) \geq n /2

, then

G

has a Hamiltonian cycle.

Theorem 24 (Ore's theorem).

G

is a simple graph on

n \geq 3

vertices such that

de g (u) + de g (v) \geq n

for every pair of non-adjacent vertices

u, v

, then

G

has a Hamiltonian cycle.

Remark 25.

Deciding the existence of an Eulerian circuit can be done in

O (∣ E ∣)

time, whereas deciding the existence of a Hamiltonian cycle is NP-complete.

For more details:

https://interconnectd.app/articles/1TJ9SYhKvLV6xsyieLaV

6. Shortest Path Problems

Definition 26 (Shortest path).

In a graph with edge weights

w : E \to R

, the shortest path from

s

t

is a path minimizing the sum of edge weights. We write

dist (s, t)

for this minimum total weight.

Key algorithms:

BFS: single-source shortest paths in unweighted graphs. $O (∣ V ∣ + ∣ E ∣)$ .
Dijkstra: single-source shortest paths with non-negative weights. $O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)$ (binary heap).
Bellman–Ford: single-source shortest paths allowing negative weights. $O (∣ V ∣∣ E ∣)$ . Also detects negative cycles.
Floyd–Warshall: all-pairs shortest paths. $O (∣ V ∣^{3})$ .
DAG shortest paths: relax edges in topological order. $O (∣ V ∣ + ∣ E ∣)$ .

Theorem 27 (Correctness of Dijkstra's algorithm).

In a graph with non-negative edge weights, Dijkstra's algorithm maintains the invariant that the distance label of every finalized vertex equals its true shortest-path distance from the source.

Theorem 28 (Negative cycle detection).

Bellman–Ford detects a negative cycle reachable from the source

s

if and only if an update occurs during the

∣ V ∣

-th iteration.

For more details:

https://interconnectd.app/articles/ffriRQaeeGIg10QEJCU1

7. Directed Graphs and Topological Sorting

Definition 29 (Strong connectivity).

A directed graph

G

is strongly connected if for every pair of vertices

u, v

there exist directed paths from

u

v

and from

v

u

. A maximal strongly connected subgraph is called a strongly connected component (SCC).

Theorem 30 (SCC condensation).

Contracting each SCC of a directed graph to a single vertex yields a DAG (directed acyclic graph).

SCC algorithms:

Kosaraju's algorithm: two passes of DFS. $O (∣ V ∣ + ∣ E ∣)$ .
Tarjan's algorithm: one pass of DFS with a stack. $O (∣ V ∣ + ∣ E ∣)$ .

Definition 31 (Topological sorting).

A topological sort of a DAG

G

is a total ordering

v_{1}, v_{2}, \dots, v_{n}

of its vertices such that

(v_{i}, v_{j}) \in A \Rightarrow i < j

Theorem 32.

A directed graph admits a topological sort

⟺

it is a DAG.

Remark 33.

Dynamic programming on a DAG proceeds in topological order, solving problems such as longest paths and path counting in

O (∣ V ∣ + ∣ E ∣)

time.

For more details:

https://interconnectd.app/articles/nNEOHtN9fe6Uf9vDnOdQ

8. Matchings and Coverings

Definition 34 (Matching).

A set of edges

M \subseteq E

in which no two edges share an endpoint is called a matching. A matching of maximum cardinality is called a maximum matching.

A bipartite graph with a matching (thick edges):

Definition 35 (Augmenting path).

An augmenting path with respect to a matching

M

is a path whose edges alternate between edges not in

M

and edges in

M

, and whose endpoints are both unmatched.

Theorem 36 (Berge's theorem).

A matching

M

is maximum

⟺

there is no augmenting path with respect to

M

Theorem 37 (Hall's marriage theorem).

In a bipartite graph

G = (X \cup Y, E)

, a perfect matching of

X

exists

⟺

∣ N (S) ∣ \geq ∣ S ∣

for every

S \subseteq X

(Hall's condition).

Theorem 38 (König's theorem).

In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

Theorem 39 (Gale–Shapley algorithm).

The stable matching problem (given preference lists for

n

agents on each side, find a matching with no blocking pair) can be solved in

O (n^{2})

time.

For more details:

https://interconnectd.app/articles/TeuUPkNltaVHPIozeFhd

9. Network Flow

Definition 40 (Flow network).

A flow network is a tuple

(G, c, s, t)

consisting of a directed graph

G = (V, A)

, a capacity function

c : A \to R_{\geq 0}

, a source

s

, and a sink

t

. A flow

f : A \to R_{\geq 0}

is a function satisfying the capacity constraint

f (e) \leq c (e)

and the conservation of flow at every vertex other than

s

and

t

Definition 41 (Cut).

For

S \subseteq V

with

s \in S

and

t \in / S

, the capacity of the cut

(S, V ∖ S)

c (S, V ∖ S) = \sum_{(u, v) \in A, u \in S, v \in / S} c (u, v)

Theorem 42 (Max-flow min-cut theorem).

The value of a maximum flow equals the capacity of a minimum cut.

Key algorithms:

Ford–Fulkerson method: iteratively find augmenting paths in the residual graph.
Edmonds–Karp: use BFS to select augmenting paths. $O (∣ V ∣∣ E ∣^{2})$ .
Dinic's algorithm: uses level graphs and blocking flows. $O (∣ V ∣^{2} ∣ E ∣)$ .

Theorem 43 (Reduction to bipartite matching).

The maximum matching in a bipartite graph can be computed by adding a source

s

and a sink

t

, assigning unit capacities, and solving the resulting maximum flow problem.

For more details:

https://interconnectd.app/articles/LvJFQmlPzZAIqGzkpcIv

10. Planar Graphs

Definition 44 (Planar graph).

A graph is planar if it can be drawn in the plane without edge crossings. Such a drawing is called a plane graph.

Theorem 45 (Euler's polyhedron formula).

For a connected plane graph

G

V - E + F = 2

where

V

is the number of vertices,

E

the number of edges, and

F

the number of faces (including the outer face).

Theorem 46 (Upper bound on edges).

In a simple connected planar graph with

∣ V ∣ \geq 3

∣ E ∣ \leq 3∣ V ∣ - 6

. In particular,

K_{5}

is not planar. If

G

is triangle-free (as in the

K_{3, 3}

case), then

∣ E ∣ \leq 2∣ V ∣ - 4

Theorem 47 (Kuratowski's theorem).

A graph

G

is planar

⟺

G

contains no subdivision of

K_{5}

K_{3, 3}

as a subgraph.

Definition 48 (Dual graph).

The dual graph

G^{*}

of a plane graph

G

has a vertex for each face of

G

, and two vertices of

G^{*}

are joined by an edge whenever the corresponding faces of

G

share a boundary edge.

For more details:

https://interconnectd.app/articles/wLP1cCOHrfu571MlDd3V

11. Graph Coloring

Definition 49 (Vertex coloring).

A vertex coloring of a graph

G

is an assignment of colors to vertices such that no two adjacent vertices receive the same color. If

G

can be colored with

k

colors,

G

is said to be

k

-colorable. The minimum such

k

is the chromatic number

χ (G)

Theorem 50 (Basic inequality).

ω (G) \leq χ (G) \leq Δ (G) + 1

where

ω (G)

is the clique number and

Δ (G)

is the maximum degree.

Theorem 51 (Brooks's theorem).

G

is a connected graph that is neither a complete graph nor an odd cycle, then

χ (G) \leq Δ (G)

Definition 52 (Chromatic polynomial).

Let

P (G, k)

denote the number of proper

k

-colorings of

G

. Then

P (G, k)

is a polynomial in

k

Theorem 53 (Vizing's theorem).

For the edge chromatic number (or chromatic index)

χ^{'} (G)

of a simple graph

G

Δ (G) \leq χ^{'} (G) \leq Δ (G) + 1

Theorem 54 (Four color theorem).

Every planar graph is

4

-colorable (

χ (G) \leq 4

Remark 55.

The four color theorem was first proved in 1976 by Appel and Haken using a computer-assisted case analysis.

For more details:

https://interconnectd.app/articles/rTuW1frjXvB379VAnpDK

12. Algebraic Graph Theory

Definition 56 (Adjacency matrix).

The adjacency matrix of a graph

G

n

vertices is the

n \times n

matrix

A = (a_{ij})

where

a_{ij} = 1

{i, j} \in E

and

a_{ij} = 0

otherwise.

Theorem 57 (Counting walks).

The

(i, j)

-entry of

A^{k}

equals the number of walks of length

k

from vertex

i

to vertex

j

Definition 58 (Laplacian matrix).

The Laplacian matrix is

L = D - A

, where

D

is the diagonal degree matrix.

L

is positive semidefinite with eigenvalues

0 \leq λ_{1} \leq λ_{2} \leq \dots \leq λ_{n}

Theorem 59 (Laplacian and connectivity).

The multiplicity of the eigenvalue

0

L

equals the number of connected components of

G

. In particular,

λ_{2} > 0 ⟺ G

is connected. The quantity

λ_{2}

is called the algebraic connectivity.

Theorem 60 (Matrix tree theorem (Kirchhoff)).

The number of spanning trees of

G

equals any cofactor of

L

(i.e., any

(i, i)

-cofactor of the Laplacian matrix).

For more details:

https://interconnectd.app/articles/VaqPp5RARg4xmSCQDDel

13. Matroids and the Greedy Algorithm

Definition 61 (Matroid).

A matroid is a pair

(E, I)

consisting of a finite set

E

and a collection

I \subseteq 2^{E}

of subsets satisfying:

$\emptyset \in I$ .
If $A \in I$ and $B \subseteq A$ , then $B \in I$ (hereditary property).
If $A, B \in I$ and $∣ A ∣ < ∣ B ∣$ , then there exists $b \in B ∖ A$ such that $A \cup {b} \in I$ (exchange property).

The members of

I

are called independent sets.

Example 62 (Graphic matroid).

Given a graph

G = (V, E)

, declare a subset of

E

to be independent if it contains no cycle. The resulting pair

(E, I)

is a matroid called the graphic matroid. Its independent sets are the forests of

G

, and its bases are the spanning trees.

Theorem 63 (Optimality of the greedy algorithm).

(E, I)

is a matroid and

w : E \to R

is a weight function, then the greedy algorithm—adding elements in decreasing order of weight, provided independence is maintained—produces a maximum-weight independent set.

Theorem 64 (Converse).

(E, I)

satisfies the hereditary property, then the greedy algorithm yields a maximum-weight independent set for every weight function

w

if and only if

(E, I)

is a matroid.

Remark 65.

For more details:

https://interconnectd.app/articles/XHUQNbZEzRsQZwUv2NGF

14. Theorem and Algorithm Directory

A one-line summary of the principal theorems and algorithms encountered in graph theory, for quick reference.

Fundamental theorems:

Handshaking lemma: $\sum de g (v) = 2∣ E ∣$ .
Bipartiteness criterion: no odd cycle $⟺$ bipartite.
Edge count of a tree: a tree on $n$ vertices has $n - 1$ edges.
Cayley's formula: the number of labeled trees on $n$ vertices is $n^{n - 2}$ .
Euler's theorem: connected $+$ all vertices of even degree $⟺$ Eulerian circuit.
Dirac's theorem: $δ (G) \geq n /2$ implies a Hamiltonian cycle.
Euler's polyhedron formula: $V - E + F = 2$ .
Kuratowski's theorem: no $K_{5}$ or $K_{3, 3}$ subdivision $⟺$ planar.
Four color theorem: every planar graph is $4$ -colorable.
Brooks's theorem: $χ (G) \leq Δ (G)$ (excluding complete graphs and odd cycles).
Vizing's theorem: $Δ (G) \leq χ^{'} (G) \leq Δ (G) + 1$ .

Matching and flow theorems:

Berge's theorem: maximum matching $⟺$ no augmenting path.
Hall's marriage theorem: $∣ N (S) ∣ \geq ∣ S ∣$ $⟺$ perfect matching exists.
König's theorem: in bipartite graphs, maximum matching $=$ minimum vertex cover.
Max-flow min-cut theorem: maximum flow $=$ minimum cut.
Menger's theorem: maximum number of independent paths $=$ minimum separating set.

Algebraic and structural theorems:

Matrix tree theorem: number of spanning trees $=$ cofactor of the Laplacian.
$A^{k}$ theorem: $(A^{k})_{ij}$ $=$ number of walks of length $k$ .
Greedy optimality: the greedy algorithm is optimal on matroids.

Key algorithms:

BFS / DFS: $O (∣ V ∣ + ∣ E ∣)$
Dijkstra: $O ((∣ V ∣ + ∣ E ∣) lo g ∣ V ∣)$
Bellman–Ford: $O (∣ V ∣∣ E ∣)$
Floyd–Warshall: $O (∣ V ∣^{3})$
Kruskal: $O (∣ E ∣ lo g ∣ E ∣)$
Prim: $O (∣ E ∣ lo g ∣ V ∣)$
Kosaraju / Tarjan (SCC): $O (∣ V ∣ + ∣ E ∣)$
Dinic (max flow): $O (∣ V ∣^{2} ∣ E ∣)$
Gale–Shapley (stable matching): $O (n^{2})$

15. Appendix: Notation and Terminology

Symbol	Name	Meaning
$G = (V, E)$	Graph	A vertex set $V$ paired with an edge set $E$
$de g (v)$	Degree	Number of edges incident to $v$
$δ (G)$	Minimum degree	$min_{v} de g (v)$
$Δ (G)$	Maximum degree	$max_{v} de g (v)$
$κ (G)$	Vertex connectivity	Min. vertices to remove to disconnect $G$
$λ (G)$	Edge connectivity	Min. edges to remove to disconnect $G$
$K_{n}$	Complete graph	The complete graph on $n$ vertices
$K_{m, n}$	Complete bipartite graph	Complete bipartite graph of sizes $m, n$
$χ (G)$	Chromatic number	Min. colors for a proper vertex coloring
$χ^{'} (G)$	Chromatic index	Min. colors for a proper edge coloring
$ω (G)$	Clique number	Size of the largest clique
$A$	Adjacency matrix	$a_{ij} = [{i, j} \in E]$
$L = D - A$	Laplacian	Degree matrix minus adjacency matrix
MST	Minimum spanning tree	Spanning tree of minimum total weight
SCC	Strongly connected component	Maximal strongly connected subgraph
DAG	Directed acyclic graph	Directed graph with no directed cycles
NP-complete	NP-complete	Hardest problems in NP (verifiable in polynomial time)

Graph Theory Discrete Mathematics Summary Theorem Reference Algorithms Competitive Programming

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

1. Introduction: How to Use This Article

2. Basic Definitions

3. Paths and Connectivity

4. Trees and Forests

5. Eulerian and Hamiltonian Graphs

6. Shortest Path Problems

7. Directed Graphs and Topological Sorting

8. Matchings and Coverings

9. Network Flow

10. Planar Graphs

11. Graph Coloring

12. Algebraic Graph Theory

13. Matroids and the Greedy Algorithm

14. Theorem and Algorithm Directory

15. Appendix: Notation and Terminology

Share your expertise with the world

More from Folio Official

Combinatorics: A Complete Summary of Definitions, Theorems, and Proofs

Number Theory: A Complete Summary of Definitions, Theorems, and Proofs

Paths and Connectivity

Directed Graphs and Topological Sorting

1. Introduction: How to Use This Article

2. Basic Definitions

3. Paths and Connectivity

4. Trees and Forests

5. Eulerian and Hamiltonian Graphs

6. Shortest Path Problems

7. Directed Graphs and Topological Sorting

8. Matchings and Coverings

9. Network Flow

10. Planar Graphs

11. Graph Coloring

12. Algebraic Graph Theory

13. Matroids and the Greedy Algorithm

14. Theorem and Algorithm Directory

15. Appendix: Notation and Terminology

Share your expertise with the world

More from Folio Official

Combinatorics: A Complete Summary of Definitions, Theorems, and Proofs

Number Theory: A Complete Summary of Definitions, Theorems, and Proofs

Paths and Connectivity

Directed Graphs and Topological Sorting