Homepage of APM 4663
Homepage of APM 4663
Office Hours: By appointment.
Handout: See Moodle.
Lectures (Updated August 11, 2025)
July 7: Introduction to concepts in graph theory.
July 8: More definitions, Havel-Hakemi Theorem.
July 9: Bipartite graphs, paths.
July 10: Characterization of bipartite graphs, balanced signed graphs, planar graphs, Euler's Formula.
July 11: Proof of 6-C Theorem, 5-C Theorem, 4-C Theorem for triangle-free planar graphs.
July 14: Kuratowski's Theorem (no proof), Eulerian graphs, Hamiltonian graphs.
July 15: Dirac's Theorem, Ore's Theorem, Bondy-Chvatal's Theorem, trees.
July 16: Went over Assignment 1, spanning trees, Kruskal's Algorithm.
July 17: Prim's Algorithm, Shortest Path, Dijkstra's Algorithm.
July 18: Maximum Flow Problem, Minimum Cut Problem.
July 21: Max-Flow Min-Cut Theorem, Ford-Fulkerson Algorithm.
July 22: Matchings, Hall's Theorem, Konig's Theorem, Tutte-Berge Formula (no proof).
July 23: Went over Assignment 2, Basic examples of counting.
July 24: Binomial Series, (ordinary) generating functions.
July 25: Combinatorial proofs, compositions of integers, closed form vs explicit formula.
July 28: Midterm test.
July 29: More compositions of integers, partitions of integers.
July 30: (Two lectures) {0,1}-strings, block decomposition.
July 31: No class.
Aug 1: More {0,1}-strings, recursive decomposition.
Aug 4: k-ary trees, planted plane trees, Lagrange Inversion Formula.
Aug 5: Exponential generating function, enumeration of permutations with respective to their cycle decomposition structures.
Aug 6: Went over Assignment 3.
Aug 7: Derangements (three proofs of the formula of the number), rooted labelled trees, Cayley's formula, Super Lagrange Inversion Formula.
Aug 8: Functional digraphs, enumerations of some special labelled graphs, distributing distinct balls into distinct boxes.
Aug 11: Brief introduction to linear programming and its applications to graph theory.
Aug 12: Went over Assignment 4.
Aug 13: Q&A.
Aug 14: Exam.