Graph Theory: Fundamental Theorems, Spanning Trees, Chromatic Polynomials, and Applications to Network Routing and Graph Colouring Problems

Abstract

Graph theory, born from Euler's 1736 solution of the Königsberg Bridge Problem, has grown into one of the most mathematically rich and practically significant branches of discrete mathematics. This paper presents a comprehensive treatment encompassing foundational definitions, fundamental theorems with proofs, spectral properties, spanning trees and the Matrix-Tree Theorem, chromatic polynomials and the Four Colour Theorem, and graph traversal algorithms with complexity analysis. The Euler characteristic V−E+F=2 for planar graphs is proved via induction; Kuratowski's planarity characterisation is stated. The theory of spanning trees is developed with full proofs of Kruskal's algorithm correctness, Cayley's formula τ(Kₙ)=n^{n−2} via the Matrix-Tree Theorem, and spanning tree count formulae for standard graph families. Chromatic polynomials are introduced via deletion-contraction and computed for standard families. The Four Colour Theorem and its applications — map colouring, register allocation, frequency assignment — are discussed. Dijkstra's shortest path algorithm is presented with full pseudocode, O((V+E)log V) complexity proof, and complete worked numerical example. Degree distribution of Erdős-Rényi random graphs and its Poisson approximation are illustrated and compared.

Cite as:

Manthan Vinod Amane. (2026). Graph Theory: Fundamental Theorems, Spanning Trees, Chromatic Polynomials, and Applications to Network Routing and Graph Colouring Problems. Journal of Applied Mathematics and Statistical Analysis, 7(2), 33–39. https://doi.org/10.5281/zenodo.21888941