A simple undirected graph is a pair $G = (V, E)$ where:
$V$ is a finite non-empty set whose elements are the vertices (or nodes);
$E \subseteq \binom{V}{2}$ is a set of unordered pairs of distinct vertices — the edges.
We write $|V| = n$ (the order) and $|E| = m$ (the size).
A directed graph (digraph) replaces $E$ by a set of ordered pairs $E \subseteq V \times V$ — the arcs. A weighted graph additionally carries a function $w : E \to \mathbb{R}$ assigning a cost to each edge.
Two vertices $u, v$ are adjacent (or neighbours) iff $\{u, v\} \in E$. An edge $e = \{u, v\}$ is incident to $u$ and to $v$.
The degree $\deg(v)$ of a vertex $v$ in an undirected graph is the number of edges incident to $v$. In a digraph: $\deg^+(v)$ (out-degree) and $\deg^-(v)$ (in-degree).
Handshake lemma. $\displaystyle \sum_{v \in V} \deg(v) = 2|E|.$ In particular the number of vertices of odd degree is even.
Each edge $\{u, v\}$ contributes $1$ to $\deg(u)$ and $1$ to $\deg(v)$, hence $2$ to the sum of degrees. Summing over all edges gives $2|E|$.
Splitting the sum by parity: $\sum_{\text{even}}\deg(v) + \sum_{\text{odd}}\deg(v) = 2|E|$. The first sum is even; the right side is even; so $\sum_{\text{odd}}\deg(v)$ is even — therefore the number of odd-degree vertices is even. $\square$
In a group of $n$ people, the number who have shaken an odd number of hands is even.
Rosen 8e §10.2 Theorem 1; Euler (1736).
5 / 31
1.3 Simple, multi, directed, weighted
Type
Definition
Self-loops?
Multi-edges?
Simple graph
edges = $\binom{V}{2}$
No
No
Multigraph
multiset of unordered pairs
No
Yes
Pseudograph
multigraph + loops
Yes
Yes
Digraph
edges $\subseteq V \times V$
Yes
No
Multidigraph
multiset of ordered pairs
Yes
Yes
Weighted graph
any of the above + $w : E \to \mathbb{R}$
Depends
Depends
Throughout this course the default is the simple finite graph; directed and weighted variants appear when needed for path-finding and network problems. Multigraphs show up mainly in Eulerian-path problems (e.g. the Königsberg bridges).
Beauquier–Berstel–Chrétienne, §6.1.
6 / 31
1.4 Special families of graphs
Notation
Name
Vertices
Edges
$K_n$
Complete graph
$n$
$\binom{n}{2}$ — every pair adjacent
$P_n$
Path
$n$
$n - 1$ — line $v_1 - v_2 - \cdots - v_n$
$C_n$
Cycle ($n \geq 3$)
$n$
$n$ — closed path
$K_{m,n}$
Complete bipartite
$m + n$
$mn$
$Q_n$
$n$-cube (hypercube)
$2^n$
$n \cdot 2^{n-1}$
$W_n$
Wheel
$n + 1$
$2n$
$S_n$
Star
$n + 1$
$n$
$K_4$ is the smallest non-planar-looking graph that is in fact planar.
$K_5$ and $K_{3,3}$ are the two minimal non-planar graphs (Kuratowski).
The hypercube $Q_3$ — vertices are 3-bit strings, edges connect strings differing in one bit — represents the corners of a cube.
Rosen 8e §10.2.
7 / 31
2.1 Representations — adjacency matrix vs list
The adjacency matrix $A \in \{0, 1\}^{n \times n}$ of a graph on $V = \{v_1, \ldots, v_n\}$ has $A_{ij} = 1$ iff $\{v_i, v_j\} \in E$. For a weighted graph, $A_{ij} = w(v_i, v_j)$ (or $+\infty$ if no edge).
The adjacency list stores, for each vertex $v$, the list $N(v)$ of its neighbours.
Aspect
Adjacency matrix
Adjacency list
Space
$\Theta(n^2)$
$\Theta(n + m)$
Check $(u,v) \in E$
$O(1)$
$O(\deg u)$
Enumerate neighbours of $v$
$O(n)$
$O(\deg v)$ — optimal
Add an edge
$O(1)$
$O(1)$ (amortised)
Dense graph ($m \approx n^2$)
Preferred
Same space, slower lookup
Sparse graph ($m \ll n^2$)
Wasteful
Preferred
Course convention: a graph is implemented as a Python dict mapping each vertex to its set/list of neighbours. We adopt this throughout.
CLRS §20.1; Beauquier–Berstel–Chrétienne §6.2.
8 / 31
2.2 Python — graphs as dicts
Throughout this course, every undirected graph $G = (V, E)$ is implemented as a Python dict mapping each vertex to the set of its neighbours:
Python — dict representation# Undirected graph on V = {a, b, c, d, e}
G = {
'a': {'b', 'c'},
'b': {'a', 'c', 'd'},
'c': {'a', 'b', 'd'},
'd': {'b', 'c', 'e'},
'e': {'d'},
}
# Basic queries — O(1) or O(deg)
def vertices(G): return G.keys()
def edges(G): return {(u, v) for u in G for v in G[u] if u < v}
def neighbours(G, v): return G[v]
def degree(G, v): return len(G[v])
def has_edge(G, u, v): return v in G[u]
# Mutation helpers
def add_vertex(G, v): G.setdefault(v, set())
def add_edge(G, u, v):
G.setdefault(u, set()).add(v)
G.setdefault(v, set()).add(u)
def remove_edge(G, u, v):
G[u].discard(v); G[v].discard(u)
print(len(vertices(G)), len(edges(G))) # 5 6
print(degree(G, 'b')) # 3
print(sorted(neighbours(G, 'b'))) # ['a', 'c', 'd']
For directed graphs, omit the symmetric assignment in add_edge: G[u].add(v) only. For weighted graphs, use a dict of dicts: G[u] = {v: weight, ...}.
Standard adjacency-list convention used throughout the course.
9 / 31
3. Subgraphs and isomorphism
$H = (V_H, E_H)$ is a subgraph of $G = (V, E)$ iff $V_H \subseteq V$ and $E_H \subseteq E \cap \binom{V_H}{2}$. $H$ is spanning if $V_H = V$, and induced if $E_H = E \cap \binom{V_H}{2}$ (all edges between $V_H$-vertices that exist in $G$).
Two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic, $G_1 \cong G_2$, iff there exists a bijection $\varphi : V_1 \to V_2$ such that $\{u, v\} \in E_1 \iff \{\varphi(u), \varphi(v)\} \in E_2$.
Isomorphism preserves all "structural" invariants — number of vertices, number of edges, degree sequence, number of triangles, chromatic number, etc. None of these is sufficient on its own to characterise isomorphism, but each can be used to refute it.
Two graphs with the same degree sequence may fail to be isomorphic. The degree sequence $(2, 2, 2, 2)$ is shared by $C_4$ and by $K_2 \sqcup K_2$ ... wait — the latter has degree sequence $(1,1,1,1)$. Better example: $C_6$ and $K_{3,3}$ both have degree sequence $(2,2,2,2,2,2)$ vs $(3,3,3,3,3,3)$ — different. Real example: two non-isomorphic graphs both with degree sequence $(3,3,3,3,3,3)$ exist on $6$ vertices ($K_{3,3}$ and the triangular prism).
Rosen 8e §10.3.
10 / 31
4.1 Walks, paths, cycles
A walk of length $k$ is a sequence $v_0 e_1 v_1 e_2 v_2 \cdots e_k v_k$ alternating vertices and edges with $e_i = \{v_{i-1}, v_i\}$.
A trail is a walk with no repeated edge.
A path is a walk with no repeated vertex.
A cycle is a closed path ($v_0 = v_k$) with $k \geq 3$.
$G$ is connected iff for every pair $u, v \in V$ there exists a path from $u$ to $v$. The connectedness relation $u \sim v$ is an equivalence relation (Lesson on Relations §3); its equivalence classes are the connected components of $G$.
A connected graph on $n$ vertices has at least $n - 1$ edges. Equality holds iff $G$ is a tree (Part II).
Induction on $n$. Base $n = 1$: $0 = n - 1$ edges, trivially connected. Step: a connected graph on $n + 1$ vertices contains a vertex $v$ with $\deg(v) \geq 1$ (else $v$ is isolated). If removing $v$ disconnects $G$, then we recurse on each component. The detail is left to slide 17. $\square$
Rosen 8e §10.4.
11 / 31
5.1 Breadth-First Search (BFS)
BFS explores the graph layer-by-layer starting from a source $s$. It produces the shortest (unweighted) distance from $s$ to every reachable vertex.
Python — BFSfrom collections import deque
def bfs(G, s):
"""Return (distance, parent) dicts from source s."""
dist = {s: 0}
parent = {s: None}
file_attente = deque([s])
while file_attente:
u = file_attente.popleft()
for v in G[u]:
if v not in dist: # unvisited
dist[v] = dist[u] + 1
parent[v] = u
file_attente.append(v)
return dist, parent
def shortest_path(G, s, t):
dist, parent = bfs(G, s)
if t not in dist: return None # not reachable
chemin = []
while t is not None:
chemin.append(t)
t = parent[t]
return list(reversed(chemin))
BFS runs in $O(n + m)$ time and produces the unique shortest-path tree rooted at $s$ (for the unweighted distance).
BFS is at the heart of every "minimum-edge-path" problem: maze solving, broadcasting, bipartite testing, shortest-step puzzles (e.g. word ladders).
CLRS §20.2; breadth-first scan / parcours en largeur.
12 / 31
5.2 Depth-First Search (DFS)
DFS dives as deep as possible before backtracking. It discovers cycles, decomposes a digraph into strongly connected components, and produces a topological order on a DAG.
Python — DFS (recursive)def dfs(G, s):
"""Recursive DFS — returns the set of visited vertices."""
vus = set()
def visite(u):
vus.add(u)
for v in G[u]:
if v not in vus:
visite(v)
visite(s)
return vus
Python — DFS (iterative with explicit stack)def dfs_iter(G, s):
vus = set()
pile = [s]
while pile:
u = pile.pop()
if u not in vus:
vus.add(u)
pile.extend(G[u])
return vus
# Number of connected components
def composantes(G):
vus, count = set(), 0
for v in G:
if v not in vus:
vus |= dfs(G, v)
count += 1
return count
DFS runs in $O(n + m)$. The recursion depth can reach $n$, so use the iterative version for graphs with long paths to avoid Python's recursion limit.
CLRS §20.3; Tarjan (1972).
13 / 31
5.3 Cycle detection & connectivity tests
Python — DFS-based cycle detection (undirected)def a_un_cycle(G):
"""True iff the graph contains at least one cycle."""
vus = set()
def visite(u, parent):
vus.add(u)
for v in G[u]:
if v not in vus:
if visite(v, u):
return True
elif v != parent:
return True # back-edge → cycle
return False
return any(visite(v, None) for v in G if v not in vus)
Python — is the graph connected?def est_connexe(G):
if not G: return True
racine = next(iter(G))
return len(dfs(G, racine)) == len(G)
Cycle detection in a directed graph uses the "gray vertex" pattern: a vertex is white (unvisited), gray (on the current DFS stack) or black (finished). A back-edge to a gray vertex signals a cycle.
CLRS §20.4.
14 / 31
6. Topological sort (DAG)
A topological order of a directed acyclic graph $G$ is a linear ordering of $V$ such that for every arc $(u, v)$, $u$ comes before $v$.
A digraph admits a topological ordering iff it is acyclic (no directed cycle).
Python — Kahn's algorithm (BFS-style)def tri_topologique(G):
"""G is a digraph as {u: list of successors}. Returns a topo order or None if cyclic."""
deg_entrant = {v: 0 for v in G}
for u in G:
for v in G[u]:
deg_entrant[v] = deg_entrant.get(v, 0) + 1
if v not in deg_entrant: deg_entrant[v] = 1
from collections import deque
file = deque([v for v in deg_entrant if deg_entrant[v] == 0])
ordre = []
while file:
u = file.popleft()
ordre.append(u)
for v in G.get(u, ()):
deg_entrant[v] -= 1
if deg_entrant[v] == 0:
file.append(v)
return ordre if len(ordre) == len(deg_entrant) else None
An Eulerian trail uses every edge of $G$ exactly once. An Eulerian circuit is a closed Eulerian trail (starting and ending at the same vertex).
Euler (1736). A connected graph has an Eulerian circuit iff every vertex has even degree. It has an Eulerian trail iff exactly $0$ or $2$ vertices have odd degree.
(⇒) Every time the walk enters a vertex it also leaves it, contributing $2$ to the degree — so all degrees must be even (or, in the open-trail case, the start and end vertex contribute one extra and have odd degree). (⇐) Construct the circuit by Hierholzer's algorithm: start at any vertex, walk along unused edges until you return; if any edges remain, splice in subcircuits at vertices that still have unused edges. Each splice is valid by the even-degree hypothesis. $\square$
Königsberg bridges (1736). Euler proved no walk crosses every bridge exactly once: the underlying multigraph has $4$ vertices of odd degree. The negative result founded graph theory.
Euler, Solutio problematis ad geometriam situs pertinentis (1736).
16 / 31
8. Hamiltonian paths and circuits
A Hamiltonian path visits every vertex exactly once. A Hamiltonian circuit is a closed Hamiltonian path.
Dirac (1952). If $G$ is simple, $n \geq 3$ and $\delta(G) \geq n/2$ (minimum degree at least half the order), then $G$ has a Hamiltonian circuit.
Ore (1960). If for every non-adjacent pair $u, v$, $\deg(u) + \deg(v) \geq n$, then $G$ has a Hamiltonian circuit. (Generalises Dirac.)
Unlike Eulerian circuits, there is no easy characterisation of Hamiltonicity. Deciding "is there a Hamiltonian circuit?" is NP-complete (Karp 1972). The travelling-salesman problem is the optimisation version.
$K_n$ ($n \geq 3$) is Hamiltonian. The Petersen graph is non-Hamiltonian but Eulerian-like.
Dirac (1952); Ore (1960); Karp (1972).
17 / 31
9. Bipartite graphs & 2-coloring
A graph $G$ is bipartite iff $V$ can be partitioned into two sets $A, B$ such that every edge connects a vertex of $A$ to a vertex of $B$ (no edge inside $A$ or inside $B$).
A graph is bipartite iff it has no odd cycle iff it is $2$-colorable.
Bipartite ⇒ no odd cycle. Any cycle alternates between $A$ and $B$, hence has even length. No odd cycle ⇒ bipartite. Run BFS from any vertex $s$; color $s$ red, its neighbours blue, then alternate. If an edge connects two same-coloured vertices, BFS finds an odd cycle. Otherwise the partition is valid. Bipartite ⇔ 2-colorable. A 2-coloring of $G$ corresponds exactly to a bipartition $A \cup B$. $\square$
Python — bipartiteness test (BFS coloring)from collections import deque
def est_biparti(G):
couleur = {}
for depart in G:
if depart in couleur: continue
couleur[depart] = 0
file = deque([depart])
while file:
u = file.popleft()
for v in G[u]:
if v not in couleur:
couleur[v] = 1 - couleur[u]
file.append(v)
elif couleur[v] == couleur[u]:
return False
return True
König (1936); Rosen 8e §10.2.
18 / 31
10. Planar graphs & Euler's formula
A graph is planar if it can be drawn in the plane with no edge crossings. A planar drawing divides the plane into faces (regions), including one unbounded face.
Euler's formula. For a connected planar graph with $n$ vertices, $m$ edges, $f$ faces: $\;n - m + f = 2.$
Induction on $m$. Base $m = n - 1$: $G$ is a tree (Part II), one face only, $n - (n-1) + 1 = 2$. ✓
Step: if $G$ has a cycle, remove one edge of the cycle; this decreases both $m$ and $f$ by $1$ (the two faces on either side of the edge merge). The formula is preserved. $\square$
For $n \geq 3$: $m \leq 3n - 6$. For bipartite planar graphs: $m \leq 2n - 4$. Hence $K_5$ (with $m = 10 > 3\cdot 5 - 6 = 9$) and $K_{3,3}$ (with $m = 9 > 2\cdot 6 - 4 = 8$) are not planar.
Kuratowski (1930). A graph is planar iff it does not contain a subdivision of $K_5$ or $K_{3,3}$.
Euler (1750); Kuratowski (1930); Rosen 8e §10.7.
19 / 31
11. Graph coloring & chromatic number
A proper $k$-coloring of $G$ is a map $c : V \to \{1, \ldots, k\}$ such that $c(u) \neq c(v)$ for every edge $\{u, v\} \in E$. The chromatic number $\chi(G)$ is the smallest $k$ for which $G$ admits a $k$-coloring.
Examples: $\chi(K_n) = n$; $\chi(C_n) = 2$ if $n$ is even, $3$ if $n$ is odd; bipartite $\Leftrightarrow \chi \leq 2$.
The 4-color theorem was the first major result proved by computer-assisted exhaustive case analysis. The 5-color theorem (every planar graph is 5-colorable) has an elegant elementary proof.
Python — greedy coloring (Welsh–Powell heuristic)def coloration_gloutonne(G):
"""Sort vertices by decreasing degree; assign smallest available color."""
ordre = sorted(G, key=lambda v: -len(G[v]))
couleur = {}
for u in ordre:
utilisees = {couleur[v] for v in G[u] if v in couleur}
c = 0
while c in utilisees: c += 1
couleur[u] = c
return couleur
Appel & Haken (1976); Welsh & Powell (1967).
20 / 31
12.1 Dijkstra — shortest paths from a source
Setting: weighted graph with non-negative weights. Goal: shortest distances from source $s$ to every vertex.
Python — Dijkstra with a heapimport heapq
def dijkstra(G, s):
"""G is a weighted graph: G[u] = {v: w, ...} with w >= 0."""
dist = {v: float('inf') for v in G}
dist[s] = 0
parent = {s: None}
tas = [(0, s)]
while tas:
d, u = heapq.heappop(tas)
if d > dist[u]: continue # stale entry
for v, w in G[u].items():
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
parent[v] = u
heapq.heappush(tas, (dist[v], v))
return dist, parent
Dijkstra runs in $O((n + m)\log n)$ using a binary heap. Correctness requires non-negative weights.
Invariant. When a vertex $u$ is popped with distance $d$, $\mathrm{dist}[u] = d_G(s, u)$ is the true shortest distance. By induction on the order of extraction: at the first extraction $s$ trivially has distance $0$. For the next: any shorter path to $u$ would go through some unextracted $v$ with $\mathrm{dist}[v] < d$, contradicting the heap property. $\square$
Python — Bellman–Forddef bellman_ford(G, s):
dist = {v: float('inf') for v in G}
dist[s] = 0
aretes = [(u, v, w) for u in G for v, w in G[u].items()]
for _ in range(len(G) - 1):
for u, v, w in aretes:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Detect negative cycle: any further relaxation = cycle
for u, v, w in aretes:
if dist[u] + w < dist[v]:
raise ValueError("Negative cycle detected!")
return dist
Bellman–Ford runs in $O(n \cdot m)$ and detects negative cycles. After $n - 1$ relaxations of every edge, all finite distances are optimal (since the longest simple path has at most $n - 1$ edges).
Bellman (1958), Ford (1956); CLRS §22.1.
22 / 31
12.3 Floyd–Warshall — all-pairs shortest paths
Floyd–Warshall computes the shortest path between every pair of vertices in $O(n^3)$ time and $O(n^2)$ space.
Python — Floyd–Warshalldef floyd_warshall(G):
sommets = list(G)
n = len(sommets)
idx = {v: i for i, v in enumerate(sommets)}
d = [[float('inf')] * n for _ in range(n)]
for i in range(n): d[i][i] = 0
for u in G:
for v, w in G[u].items():
d[idx[u]][idx[v]] = w
# Core triple loop — "via vertex k" relaxation
for k in range(n):
for i in range(n):
for j in range(n):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
return sommets, d
Idea. Define $d^{(k)}_{ij}$ = shortest $i \to j$ path using only intermediate vertices in $\{1, \ldots, k\}$. The recurrence $d^{(k)}_{ij} = \min(d^{(k-1)}_{ij},\; d^{(k-1)}_{ik} + d^{(k-1)}_{kj})$ is the heart of the algorithm — a textbook dynamic-programming pattern.
Floyd (1962); Warshall (1962); CLRS §23.
23 / 31
13.1 Minimum spanning tree — Kruskal
A spanning tree of a connected graph $G$ is a subgraph that is a tree and contains every vertex. A minimum spanning tree (MST) minimises the total edge weight.
Kruskal's algorithm: sort edges by weight; greedily add the next-lightest edge whose endpoints lie in different connected components (use Union-Find).
Python — Kruskal with Union-Finddef kruskal(G):
"""G weighted (G[u] = {v: w, ...}). Returns list of edges in MST."""
parent = {v: v for v in G}
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
def union(x, y):
rx, ry = find(x), find(y)
if rx == ry: return False
parent[rx] = ry
return True
aretes = sorted(((w, u, v) for u in G for v, w in G[u].items() if u < v))
mst = []
for w, u, v in aretes:
if union(u, v):
mst.append((u, v, w))
if len(mst) == len(G) - 1: break
return mst
Kruskal runs in $O(m \log m)$ via the sort.
Kruskal (1956); CLRS §21.2.
24 / 31
13.2 Minimum spanning tree — Prim
Prim's algorithm grows the MST one vertex at a time from a single seed, always adding the lightest edge leaving the current tree.
Python — Prim with a heapimport heapq
def prim(G, depart=None):
if depart is None: depart = next(iter(G))
dans_arbre = {depart}
mst = []
tas = [(w, depart, v) for v, w in G[depart].items()]
heapq.heapify(tas)
while tas and len(dans_arbre) < len(G):
w, u, v = heapq.heappop(tas)
if v in dans_arbre: continue
dans_arbre.add(v)
mst.append((u, v, w))
for x, wx in G[v].items():
if x not in dans_arbre:
heapq.heappush(tas, (wx, v, x))
return mst
Prim runs in $O((n + m)\log n)$ with a binary heap, $O(m + n \log n)$ with a Fibonacci heap.
Both Kruskal and Prim rely on the cut property: in any cut of the graph, the lightest edge crossing the cut belongs to some MST. (Used as a loop invariant in the correctness proof.)
Python — what to import for graph & tree workfrom collections import deque # BFS queue
import heapq # Dijkstra, Prim, heaps
import functools # reduce, lru_cache
# Adjacency-list graph
G = {'a': {'b': 3, 'c': 1}, 'b': {'a': 3, 'c': 7}, 'c': {'a': 1, 'b': 7}}
# Binary tree
T = [1, [2, [4, [], []], [5, [], []]], [3, [], [6, [], []]]]
# Optional: NetworkX for sanity checks (a library, not for the from-scratch exercises)
# import networkx as nx
# nx_G = nx.Graph()
# nx_G.add_weighted_edges_from([(u, v, w) for u in G for v, w in G[u].items() if u < v])
# nx.shortest_path(nx_G, 'a', 'b', weight='weight')
In exercises and assessments, do not rely on NetworkX — students are expected to implement BFS, DFS, Dijkstra, Kruskal/Prim, and tree operations from scratch using the standard dict and list representations. NetworkX is a convenient sanity check, not a substitute for the explicit implementations.
29 / 31
Bibliography
K. H. Rosen. Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019 — §§10.1–10.7 (graphs), §§11.1–11.5 (trees).
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, 4th ed., MIT Press, 2022 — Part VI (graph algorithms), ch. 12–13 (BST, balanced trees), ch. 6 (heaps).
D. Beauquier, J. Berstel, P. Chrétienne. Éléments d'algorithmique, Masson, 1992 — standard French-language algorithmics reference.
R. Diestel. Graph Theory, 5th ed., Springer, 2017 — standard mathematical reference.
D. E. Knuth. The Art of Computer Programming, vol. 1 (Fundamental Algorithms), vol. 3 (Sorting and Searching), Addison-Wesley.
H. Abelson & G. J. Sussman. Structure and Interpretation of Computer Programs, 2nd ed., MIT Press, 1996 — §2.2 (tree-like data).
L. Euler (1736). Solutio problematis ad geometriam situs pertinentis — origins of graph theory.
K. Appel & W. Haken (1976). Four-color theorem.
E. W. Dijkstra (1959). A note on two problems in connexion with graphs, Numer. Math. 1.
S. S. Skiena. The Algorithm Design Manual, 3rd ed., Springer, 2020 — graphs and trees from the algorithms-engineering perspective.