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.
Explores binary relations on sets, relation properties (reflexive, symmetric, transitive), equivalence relations, and partitions. Covers composition of relations, inverse relations, and how relations connect to graphs with directed edges and multigraphs.
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.