Graph Theory Reference

Part I. Foundations of Graph Theory

Chapter	Title
1	What Graph Theory Is
2	Basic Definitions
3	Vertices and Edges
4	Graph Representations
5	Degree of a Vertex
6	Walks, Trails, and Paths
7	Cycles and Circuits
8	Connected Graphs
9	Components
10	Isomorphism
11	Subgraphs
12	Graph Operations
13	Complement Graphs
14	Graph Invariants
15	Classes of Graphs

Part II. Directed and Weighted Graphs

Chapter	Title
16	Directed Graphs
17	In-Degree and Out-Degree
18	Directed Paths and Cycles
19	Strong Connectivity
20	Directed Acyclic Graphs
21	Topological Ordering
22	Weighted Graphs
23	Multigraphs
24	Hypergraphs
25	Signed and Labeled Graphs

Part III. Trees and Forests

Chapter	Title
26	Trees
27	Forests
28	Rooted Trees
29	Binary Trees
30	Spanning Trees
31	Minimum Spanning Trees
32	Prüfer Sequences
33	Tree Traversal
34	Tree Decomposition
35	Applications of Trees

Part IV. Planar and Geometric Graphs

Chapter	Title
36	Planar Graphs
37	Plane Embeddings
38	Euler’s Formula
39	Faces and Regions
40	Kuratowski’s Theorem
41	Graph Coloring of Planar Graphs
42	Dual Graphs
43	Geometric Graphs
44	Intersection Graphs
45	Computational Geometry Connections

Part V. Connectivity and Network Structure

Chapter	Title
46	Vertex Connectivity
47	Edge Connectivity
48	Cuts and Cut Sets
49	Bridges and Articulation Points
50	Menger’s Theorem
51	Network Reliability
52	Expansion and Expanders
53	Graph Separators
54	Sparse and Dense Graphs
55	Random Walks on Graphs

Part VI. Matching and Covering

Chapter	Title
56	Matchings
57	Perfect Matchings
58	Hall’s Marriage Theorem
59	Bipartite Matching
60	Maximum Matching Algorithms
61	Vertex Covers
62	Edge Covers
63	Independent Sets
64	Cliques
65	Dominating Sets

Part VII. Coloring Theory

Chapter	Title
66	Vertex Coloring
67	Edge Coloring
68	Chromatic Number
69	Chromatic Polynomial
70	Greedy Coloring
71	Brooks’ Theorem
72	Perfect Graphs
73	Ramsey Theory
74	List Coloring
75	Fractional Coloring

Part VIII. Algebraic Graph Theory

Chapter	Title
76	Adjacency Matrices
77	Incidence Matrices
78	Laplacian Matrices
79	Spectrum of a Graph
80	Eigenvalues and Eigenvectors
81	Spectral Theorems
82	Algebraic Connectivity
83	Expander Graphs
84	Graph Energy
85	Cayley Graphs
86	Automorphism Groups

Part IX. Probabilistic and Random Graphs

Chapter	Title
87	Random Graph Models
88	Erdős-Rényi Graphs
89	Threshold Phenomena
90	Small-World Networks
91	Scale-Free Networks
92	Preferential Attachment
93	Percolation on Graphs
94	Probabilistic Methods
95	Random Processes on Networks

Part X. Graph Algorithms

Chapter	Title
96	Graph Traversal Algorithms
97	Breadth-First Search
98	Depth-First Search
99	Shortest Paths
100	Dijkstra’s Algorithm
101	Bellman-Ford Algorithm
102	Floyd-Warshall Algorithm
103	Network Flow
104	Maximum Flow Algorithms
105	Minimum Cut Algorithms
106	Matching Algorithms
107	Union-Find Structures
108	Dynamic Graph Algorithms
109	Approximation Algorithms
110	Randomized Algorithms

Part XI. Computational Complexity

Chapter	Title
111	Complexity Classes
112	NP-Complete Graph Problems
113	Hamiltonian Paths and Cycles
114	Traveling Salesman Problem
115	Graph Isomorphism Problem
116	Parameterized Complexity
117	Fixed-Parameter Tractability
118	Approximation Hardness

Part XII. Advanced Topics

Chapter	Title
119	Extremal Graph Theory
120	Turán-Type Problems
121	Szemerédi Regularity Lemma
122	Minor Theory
123	Robertson-Seymour Theory
124	Infinite Graphs
125	Topological Graph Theory
126	Category-Theoretic Graphs
127	Simplicial Complexes
128	Graph Limits
129	Temporal Graphs
130	Quantum Graph Theory

Part XIII. Applications

Chapter	Title
131	Social Networks
132	Web Graphs
133	Search Engines and PageRank
134	Biological Networks
135	Chemical Graph Theory
136	Electrical Networks
137	Transportation Networks
138	Communication Networks
139	Compiler Dependency Graphs
140	Knowledge Graphs
141	Recommendation Systems
142	Machine Learning on Graphs
143	Graph Neural Networks
144	Distributed Systems
145	Blockchain and Peer-to-Peer Networks

Part XIV. Specialized Structures

Chapter	Title
146	Bipartite Graphs
147	Complete Graphs
148	Regular Graphs
149	Interval Graphs
150	Chordal Graphs
151	Comparability Graphs
152	Perfect Graphs
153	Tournament Graphs
154	Grid Graphs
155	De Bruijn Graphs
156	Kneser Graphs
157	Petersen Graph
158	Ramanujan Graphs

Appendices

Appendix	Title
A	Set Theory and Relations
B	Proof Techniques
C	Linear Algebra for Graph Theory
D	Probability Review
E	Algorithms and Complexity
F	Mathematical Notation
G	Historical Development
H	Common Graph Families
I	Theorem Index
J	Symbol Index

This structure moves from elementary graph concepts toward structural theory, algorithms, algebraic methods, probabilistic models, and modern applications. It supports both pure mathematical treatment and computational graph systems used in computer science, networks, optimization, and machine learning.

I. Foundations of Graph TheoryBasic definitions, vertices and edges, graph representations, degree, walks, paths, cycles, connectivity, isomorphism, subgraphs, and classes of graphs — the bedrock of graph theory.

15 pages · 135 min

II. Directed and Weighted GraphsDirected graphs, in-degree and out-degree, directed paths and cycles, strong connectivity, DAGs, topological ordering, weighted graphs, multigraphs, hypergraphs, and labeled graphs.

10 pages · 103 min

III. Trees and ForestsTrees, forests, rooted and binary trees, spanning trees, minimum spanning trees, Prüfer sequences, tree traversal, tree decomposition, and applications of trees.

10 pages · 89 min

IV. Planar and Geometric GraphsPlanar graphs, plane embeddings, Euler's formula, faces, Kuratowski's theorem, coloring of planar graphs, dual graphs, geometric graphs, and connections to computational geometry.

10 pages · 76 min

V. Connectivity and Network StructureVertex and edge connectivity, cuts, bridges, articulation points, Menger's theorem, network reliability, expanders, separators, and random walks on graphs.

10 pages · 95 min

VI. Matching and CoveringMatchings, perfect matchings, Hall's marriage theorem, bipartite matching, maximum matching algorithms, vertex and edge covers, independent sets, cliques, and dominating sets.

10 pages · 80 min