Defines graphs as discrete structures consisting of vertices and edges representing symmetric, irreflexive relations. Provides practical applications including social networks, geography, travel routing, and delivery optimization. Discusses various other discrete structures briefly.
Covers perfect matchings in bipartite graphs, Hall’s Marriage Theorem with necessary and sufficient conditions, alternating and augmenting paths, and applications to assignment problems. Includes vertex covers and maximal partial matchings.
Comprehensive study of graph vertex coloring and edge coloring. Covers chromatic number, Four Color Theorem for planar graphs, chromatic index, clique numbers, Brooks’ Theorem, and Vizing’s Theorem with applications to scheduling and map coloring.
Covers Euler trails and circuits (traversing every edge exactly once) with necessary and sufficient conditions based on vertex degrees. Contrasts with Hamilton paths (visiting every vertex exactly once) and discusses the NP-complete nature of Hamilton path problems.
Study of planar graphs, Euler’s formula (v-e+f=2), and applications to polyhedra. Proves K5 and K3,3 are non-planar, discusses faces, and applies Euler’s formula to regular polyhedra including tetrahedron, cube, and dodecahedron.