Fundamentals of Graph Theory

Comprehensive Lecture Notes & Reference Guide

Kanak Waingankar

Academic Year 2026–2027

Contents

1 Introduction to Graph Theory 3

1.1 Historical Context & The Seven Bridges of Königsberg . . . . . . . . . . . . . . . 3
1.2 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Degree of Vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Types of Graphs 4
2.1 Simple and Multigraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Complete Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 Regular Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Trees and Arborescences 5

3.1 Properties of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Rooted Trees and Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.3 Spanning Trees & Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . 5

4 Connectivity & Paths 6

4.1 Walks, Trails, Paths, and Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.2 Vertex and Edge Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.3 Menger’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

5 Eulerian and Hamiltonian Graphs 7

5.1 Eulerian Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
5.2 Hamiltonian Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

6 Matrix Representations & Spectral Graph Theory 8

6.1 Adjacency Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.2 Incidence Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6.3 Laplacian Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

7 Planar Graphs 9
7.1 Planarity Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.2 Euler’s Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.3 Kuratowski’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

8 Graph Coloring 10
8.1 Vertex Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8.2 Four Color Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8.3 Edge Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1
CONTENTS Graph Theory Notes

9 Matchings & Network Flows 11

9.1 Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
9.2 Network Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

10 Fundamental Graph Algorithms 12

10.1 Graph Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
10.2 Shortest Path Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2
Chapter 1

Introduction to Graph Theory

1.1 Historical Context & The Seven Bridges of Königsberg

Graph theory originated in 1736 when Leonhard Euler solved the famous Seven Bridges of
Königsberg problem. The city of Königsberg was set on both sides of the Pregel River and
included two large islands connected to each other and the mainlands by seven bridges. Euler
proved that it was impossible to cross each bridge exactly once and return to the starting point,
giving birth to topology and graph theory.

1.2 Basic Definitions

Definition 1.1 (Graph). A graph G = (V, E) consists of a set V of vertices (or nodes) and
a set E ⊆ V × V of edges (or links).

Definition 1.2 (Order and Size). For a graph G = (V, E):

• The order of G, denoted by |V | or n, is the number of vertices.

• The size of G, denoted by |E| or m, is the number of edges.

1.3 Degree of Vertices

Definition 1.3 (Degree). The degree of a vertex v ∈ V , denoted by deg(v) or d(v), is the
number of edges incident to v.

Theorem 1.1 (Handshaking Lemma). For any finite undirected graph G = (V, E):
X
deg(v) = 2|E|
v∈V

Proof. Every edge e = (u, v) ∈ E contributes exactly 1 to the degree of vertex u and 1 to the
degree of vertex v. Therefore, summing the degrees over all vertices counts each edge exactly
twice.

Corollary 1.2. In any graph, the number of vertices with odd degree is always even.

3
Chapter 2

Types of Graphs

2.1 Simple and Multigraphs

A simple graph contains no loops (edges connecting a vertex to itself) and no parallel edges
(multiple edges connecting the same pair of vertices). A graph containing parallel edges or loops
is termed a multigraph.

2.2 Complete Graphs

A complete graph Kn is a simple graph with n vertices in which every pair of distinct vertices
is connected by a unique edge.
 
n n(n − 1)
|E(Kn )| = =
2 2

2.3 Bipartite Graphs

Definition 2.1 (Bipartite Graph). A graph G = (V, E) is bipartite if V can be partitioned
into two disjoint sets V1 and V2 such that every edge e ∈ E connects a vertex in V1 to a vertex
in V2 .

Theorem 2.1 (Characterization of Bipartite Graphs). A graph G is bipartite if and only if it

contains no odd cycles.

2.4 Regular Graphs

A graph is k-regular if every vertex has degree k. A 3-regular graph is often referred to as a
cubic graph.

4
Chapter 3

Trees and Arborescences

3.1 Properties of Trees

Definition 3.1 (Tree). A tree is a connected, acyclic simple graph. A collection of disjoint
trees is called a forest.

Theorem 3.1 (Equivalent Conditions for Trees). Let G = (V, E) be an undirected graph with
n vertices. The following are equivalent:

1. G is a tree.

2. G is connected and has n − 1 edges.

3. G is acyclic and has n − 1 edges.

4. There exists a unique path between any two distinct vertices in G.

5. G is minimally connected (removing any edge disconnects G).

6. G is maximally acyclic (adding any edge creates a unique cycle).

3.2 Rooted Trees and Traversal

In a rooted tree, one node is designated as the root. Terminology includes:

• Parent and Child: Vertices adjacent on the path to the root.

• Leaf: A node with no children (degree 1 in unrooted trees).

• Height: The maximum depth among all nodes in the tree.

3.3 Spanning Trees & Minimum Spanning Trees

For a connected graph G, a spanning tree T is a subgraph that includes all vertices of G and
is a tree. P
For edge-weighted graphs, the Minimum Spanning Tree (MST) minimizes e∈T w(e).

• Kruskal’s Algorithm: A greedy edge-sorting approach using Union-Find (O(E log V )).

• Prim’s Algorithm: A priority-queue vertex-expansion approach (O(E + V log V )).

5
Chapter 4

Connectivity & Paths

4.1 Walks, Trails, Paths, and Cycles

• Walk: An alternating sequence of vertices and edges.

• Trail: A walk with no repeated edges.

• Path: A walk with no repeated vertices.

• Cycle: A closed trail with no repeated vertices except start/end.

4.2 Vertex and Edge Connectivity

Definition 4.1 (Vertex Connectivity). The vertex connectivity κ(G) is the minimum number
of vertices whose removal disconnects G or leaves a single vertex.

Definition 4.2 (Edge Connectivity). The edge connectivity λ(G) is the minimum number
of edges whose removal disconnects G.

Theorem 4.1 (Whitney’s Inequality). For any graph G:

κ(G) ≤ λ(G) ≤ δ(G)

where δ(G) is the minimum degree of G.

4.3 Menger’s Theorem

Theorem 4.2 (Menger’s Theorem). Let u and v be non-adjacent vertices in G. The minimum
number of vertices needed to disconnect u and v equals the maximum number of pairwise vertex-
disjoint paths between u and v.

6
Chapter 5

Eulerian and Hamiltonian Graphs

5.1 Eulerian Graphs

An Eulerian trail visits every edge exactly once. An Eulerian circuit is a closed Eulerian
trail.

Theorem 5.1 (Euler’s Theorem). A connected graph G has an Eulerian circuit if and only if
every vertex in G has an even degree.

5.2 Hamiltonian Graphs

A Hamiltonian cycle visits every vertex in G exactly once (except start/end).
n
Theorem 5.2 (Dirac’s Theorem). If G is a simple graph with n ≥ 3 vertices and deg(v) ≥ 2
for all v ∈ V , then G is Hamiltonian.

Theorem 5.3 (Ore’s Theorem). If G is a simple graph with n ≥ 3 vertices such that deg(u) +
deg(v) ≥ n for every non-adjacent pair u, v, then G is Hamiltonian.

7
Chapter 6

Matrix Representations & Spectral

Graph Theory

6.1 Adjacency Matrix

For a simple graph G with vertices v1 , v2 , . . . , vn , the adjacency matrix A ∈ Rn×n is defined
by: (
1 if (vi , vj ) ∈ E
Aij =
0 otherwise

Theorem 6.1. The (i, j)-th entry of Ak represents the number of walks of length k between
vertex vi and vertex vj .

6.2 Incidence Matrix

The incidence matrix M ∈ Rn×m relates vertices to edges:
(
1 if vertex vi is incident to edge ej
Mij =
0 otherwise

6.3 Laplacian Matrix

The Laplacian matrix L = D − A, where D is the diagonal degree matrix (diag(deg(vi ))).

Theorem 6.2 (Matrix Tree Theorem). The number of spanning trees in a connected simple
graph G equals any cofactor of its Laplacian matrix L.

8
Chapter 7

Planar Graphs

7.1 Planarity Definition

A graph G is planar if it can be drawn in the 2D plane such that no two edges intersect except
at a common vertex.

7.2 Euler’s Formula

Theorem 7.1 (Euler’s Planar Formula). For any connected planar graph drawn in a plane with
V vertices, E edges, and F faces:
V −E+F =2

Corollary 7.2. For a simple planar graph with V ≥ 3:

E ≤ 3V − 6

7.3 Kuratowski’s Theorem

Theorem 7.3 (Kuratowski’s Theorem). A finite graph is planar if and only if it does not
contain a subgraph that is a subdivision of K5 or K3,3 .

9
Chapter 8

Graph Coloring

8.1 Vertex Coloring

A k-coloring of a graph G assigns one of k colors to each vertex such that no adjacent vertices
share the same color. The chromatic number χ(G) is the minimum k required.

8.2 Four Color Theorem

Theorem 8.1 (Four Color Theorem). Every planar graph is 4-colorable (χ(G) ≤ 4).

8.3 Edge Coloring

An edge coloring assigns colors to edges so no incident edges share a color. The chromatic
index χ′ (G) is the minimum colors needed.

Theorem 8.2 (Vizing’s Theorem). For any simple graph G with maximum degree ∆:

∆ ≤ χ′ (G) ≤ ∆ + 1

10
Chapter 9

Matchings & Network Flows

9.1 Matchings
A matching M ⊆ E is a set of edges without common vertices. A matching is perfect if it
saturates all vertices in G.

Theorem 9.1 (Hall’s Marriage Theorem). A bipartite graph G = (V1 ∪ V2 , E) has a matching
that saturates V1 if and only if for every subset S ⊆ V1 :

|N (S)| ≥ |S|

where N (S) is the neighborhood of S.

9.2 Network Flows

A flow network G = (V, E) has a source s, sink t, and capacities c(u, v).

Theorem 9.2 (Max-Flow Min-Cut Theorem). The maximum amount of flow passing from s
to t equals the minimum capacity of an s-t cut.

11
Chapter 10

Fundamental Graph Algorithms

10.1 Graph Traversal

• Breadth-First Search (BFS): Explores level by level using a queue (O(V + E)). Com-
putes shortest paths in unweighted graphs.

• Depth-First Search (DFS): Explores along branches using a stack or recursion (O(V +
E)). Computes topological sorts and connected components.

10.2 Shortest Path Algorithms

1. Dijkstra’s Algorithm: Finds single-source shortest paths for non-negative weights in
O((V + E) log V ) time using Fibonacci heaps.

2. Bellman-Ford Algorithm: Handles negative edge weights in O(V E) time.

3. Floyd-Warshall Algorithm: Computes all-pairs shortest paths in O(V 3 ) time.

12