Discrete Mathematics I

Syllabus

• Strategy games and chessboard-type games (introductory problems).
• Counting principles: permutations, variations, combinations (with/without repetition).
• Inclusion–exclusion principle and variants; recursion and Fibonacci-type arguments; difference sequences.
• Pigeonhole principle with combinatorial and geometric applications; averaging and double counting.
• Binomial coefficients and identities; guessing games (e.g., Bar-Kochba variants, counterfeit coin problems).
• Methods for proving impossibility (invariants, parity, extremal arguments).
• Graph basics: loops/multiple edges/simple graphs; degree sum formula and applications; walks/paths/cycles.
• Connectivity and components; trees/forests and edge counts; Euler trails/circuits (undirected and directed analogues).
• Directed graphs, tournaments, Hamilton paths/cycles (necessary and sufficient conditions; tournament Hamilton paths).
• Round-robin scheduling; 1-factorizations of complete graphs.
• Graph algorithms: BFS, maze traversal; weighted graphs (Kruskal, Dijkstra).
• Planar graphs: Euler formula; Kuratowski theorem; coloring and chromatic number; 6-, 5-, 4-color theorems (statements).
• Ramsey theory for graphs and set systems (statements); Erdős lower bound idea; “Happy Ending” problem.
• Extremal graph theory: Erdős–Stone–Simonovits theorem (statement); forbidden subgraph estimates; finite geometries (selected constructions).