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)