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.
Comprehensive coverage of trees as connected acyclic graphs and forests. Includes properties of trees (unique paths, vertex degrees), spanning trees, rooted trees with parent-child relationships, and proof that trees have v-1 edges.