Syllabus:
Module-0: Preliminaries (1 week)
Isomorphisms & Automorphisms; Subgraphs & Supergraphs; Paths & Cycles; Connectedness; Special Graph Families; Connections with Complexity & Algorithms; Bipartiteness; Eulerian tours vs Hamiltonian cycles
Module-1: Cycle Space & Bond Space (1.5 weeks)
Cycles & Even Subgraphs; The Cycle Space; Orthogonality; Orthogonal Complement; Cuts & Bonds; The Bond Space
Module-2: Connectivity (3.5 weeks)
Nonseparable graphs; Block & Ear Decompositions; Vertex & edge Connectivity; Menger's Theorems; Dirac's Theorem; edge contraction; 3-connected graphs; Thomassen's Theorem & Tutte's Wheel Theorem
Module-3: Planarity (3 weeks)
Planarity & the Jordan Curve Theorem; containment notions; Kuratowski vs Wagner; Faces, Plane Duality & Nonseparability; Euler's formula & its implications; Tutte's Theory of Bridges; Planarity Testing; Nonseparating cycles & 3-connectedness
Module-4: Colorings (2 weeks)
Brief history of the 4 Color Problem; 5 Color Theorem & Heawood's Proof; Edge Colorings & Matchings; Tait's Formulation of the 4 Color Problem; Tait's Theorem; Chromatic Number & Bounds; Greedy Heuristic; Brooks' Theorem
Module-5: Matchings (3 weeks)
Alternating paths/cycles & Augmenting paths; Berge's Theorem; Bipartite Matchings, Hall's & Konig-Egervary Theorems; Edge Colorings, Vizing's Theorem & Snarks; Barriers; Tutte-Berge Formula & Tutte's Theorem; Petersen's Theorem