CS6240-2021
Structural Graph Theory
Module-1: Preliminaries
Lecture-2 (Standard Terminology and Graph Families)
Lecture-3 (Bipartite Graphs versus Odd Cycles)
Lecture-4 (Cycle Space)
Lecture-5 (Even subgraphs versus Cuts)
Lecture-6 (Bond Space)Module-2: Connectivity
Lecture-7 (Cut-edges and the Cycle Double Cover conjecture)
Lecture-8 (Separating vertices and Nonseparable Graphs)
Lecture-9 (Block Decompositions and Ear Decompositions)
Lecture-10 (Vertex Connectivity)
Lecture-11 (Menger's Theorem)
Lecture-12 (Menger's Theorem and Vertex Connectivity)
Lecture-13 (Applications of Menger's Theorem and Edge Connectivity)
Lecture-14 (3-connected Graphs and their relevance)
Lecture-15 (Generating 3-connected Graphs)
Lecture-16 (3-connected Graphs: Thomassen's Theorem)
Lecture-17 (Generating simple 3-connected graphs: Tutte's Wheel Theorem)
Lecture-18 (Tutte's Wheel Theorem: proof)Module-3: Planarity
Lecture-19 (Planarity and the Jordan Curve Theorem)
Lecture-20 (Kuratowski's Theorem: statement)
Lecture-21 (Planar Duality I)
Lecture-22 (Planar Duality II)
Lecture-23 (Euler's Formula and Bridges of Cycles)
Lecture-24 (Bridges of Cycles and Nonseparating Cycles)
Lecture-25 (Minors versus Subdivisions, Wagner versus Kuratowski)
Lecture-26 (Wagner's Theorem: proof)Module-4: Vertex Colorings
Lecture-27 (The Four Color Problem)
Lecture-28 (The Five Color Theorem)
Lecture-29 (Heawood's proof of 5CT and Tait's Theorem)
Lecture-30 (Tait's Theorem: proof)
Lecture-31 (Chromatic number and bounds)
Lecture-32 (Brooks' Theorem: proof)Module-5: Bipartite Matchings and Edge Colorings
Lecture-33 (Matchings and Augmenting Paths)
Lecture-34 (Bipartite Matchings and Hall's Theorem)
Lecture-35 (Matchings versus Vertex Covers, and Konig-Egervary Theorem)
Lecture-36 (Vizing's Theorem: statement, and Snarks)
Lecture-37 (Edge Colorings of Bipartite Graphs)
Lecture-38 (Vizing's Theorem: proof)Module-6: Matchings
Lecture-39 (Tutte's Theorem: statement; Tutte-Berge Theorem: statement; Petersen's Theorem: proof)
Lecture-40 (Tutte-Berge Theorem: Gallai's proof)
Lecture-41 (Gallai's Lemma: proof)
Lecture-42 (Perfect Matchings: counting and covering)
Lecture-43 (Pfaffian Orientations and Graphs)
Lecture-44 (Pfaffian Orientations and Conformal cycles)
Lecture-45 (Kasteleyn's Theorem: proof ingredients)
Lecture-46 (Little's Theorem: statement)
Lecture-47 (Tight Cut Decomposition and Lovasz's Uniqueness Theorem)
Lecture-48 (Structural Characterization of Pfaffian Braces)