Introduction to counting using Pascal’s triangle. Covers lattice paths, bit strings, subsets, and binomial coefficients. Explains how Pascal’s triangle relates to combinations, the choose notation, and applications to pizza toppings and handshake problems.
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.