CS6240-2021
Structural Graph Theory

Module-0: Preliminaries
Lecture-1 (Definitions & Terminology)
Lecture-2 (Terminology, Isomorphism, Connectedness & Special Graph Families)
Lecture-3 (Connections with Complexity/Algorithms; Bipartite versus Odd Cycles)
Lecture-4 (Bipartite versus Odd Cycles; Eulerian trails & tours)

Module-1: Cycle Space & Bond Space
Lecture-5 (Cycles & Even Subgraphs)
Lecture-6 (The Cycle Space; Orthogonality)
Lecture-7 (Orthogonal complement)
Lecture-8 (Cuts & Bonds)
Lecture-9 (The Bond Space; Summary of Module-1)

Module-2: Connectivity
Lecture-10 (Cut-edges & cut-vertices; the Cycle Double Cover conjecture)
Lecture-11 (Separating vertices & Nonseparable graphs)
Lecture-12 (Blocks & the Block Decomposition)
Lecture-13 (Ear Decompositions of Nonseparable graphs)
Lecture-14 (Odd versus Even Cycles; Vertex-connectivity)
Lecture-15 (Menger's Theorem)
Lecture-16 (Vertex-connectivity: a different viewpoint)
Lecture-17 (Dirac's Theorem; Edge-connectivity)
Lecture-18 (Edge-connectivity & Edge-contraction)
Lecture-19 (A theory of 3-connected graphs)
Lecture-20 (Generating 3-connected graphs; Thomassen's Theorem)
Lecture-21 (Generating simple 3-connected graphs; Wheels)
Lecture-22 (Tutte's Wheel Theorem: proof part-I)
Lecture-23 (Tutte's Wheel Theorem: proof part-II; Minors & 3-connectedness)

Module-3: Planarity
Lecture-24 (Planarity & the Jordan Curve Theorem)
Lecture-25 (Nonplanarity of K_5 & K_{3,3}; Graph containment notions)
Lecture-26 (Kuratowski versus Wagner; Faces of a Plane Graph)
Lecture-27 (Nonseparable plane graphs; Plane Duality: definitions & examples)
Lecture-28 (Connectivity in the shadow of Plane Duality)
Lecture-29 (Cycle/Bond Spaces & Plane Duality; Facial isomorphism & Euler's Formula)
Lecture-30 (Sparsity of simple Planar Graphs; Tutte's Theory of Bridges)
Lecture-31 (Tutte's Theory of Bridges: avoiding and overlapping bridges)
Lecture-32 (Skew versus Equivalent 3-bridges; Nonseparating cycles)
Lecture-33 (Planarity & 3-connectedness)
Lecture-34 (Proof of Wagner's Theorem; Beyond CS6240: Planarity Testing Algorithm)

Module-4: Colorings
Lecture-35 (A brief history of the Four Color Theorem; proof: Six Colors suffice)
Lecture-36 (The Five Color Theorem & Heawood's Proof)
Lecture-37 (Edge Colorings & Matchings; Tait's Formulation of the Four Color Conjecture)
Lecture-38 (Tait's Theorem & proof; Tait's false conjecture & Barnette's Conjecture)
Lecture-39 (Chromatic Number & Bounds; Greedy Heuristic)
Lecture-40 (Brooks' Theorem & Lovasz's Proof)

Module-5: Matchings
Lecture-41 (Alternating paths/cycles & Augmenting paths; Berge's Theorem)
Lecture-42 (Bipartite Matchings; Hall's Theorem & proof)
Lecture-43 (Matchings versus Vertex Covers; Konig-Egervary Theorem & proof)
Lecture-44 (Edge Colorings; Vizing's Theorem statement: Class-1 & Class-2 graphs; Snarks)
Lecture-45 (Bipartite Edge Colorings; Swapping Colors: a key idea for edge coloring proofs)
Lecture-46 (An application of Bipartite Matchings: Vizing's Theorem & proof part - I)
Lecture-47 (An application of Bipartite Matchings: Vizing's Theorem & proof part - II)
Lecture-48 (Vizing's Theorem generalization; Matchings: from bipartite to all graphs)
Lecture-49 (Barriers; Tutte-Berge Formula & Tutte's Theorem; Petersen's Theorem & proof)
Lecture-50 (Essential & Inessential vertices; Hypomatchable Graphs)
Lecture-51 (Tutte-Berge Theorem & proof; Cubic Graphs; Berge & Fulkerson Conjectures)

Module-6: Special Topic in Matchings --- Disconnected 2-Factors in Cubic Graphs
Lecture-52 (2-factors and Hamiltonian Cycles in Cubic Graphs; Diwan's Theorem)
Lecture-53 (Matching Covered Graphs; Tight Cuts & Tight Cut Decomposition; Bricks & Braces)
Lecture-54 (A conjecture characterizing "2-factor Hamiltonian" Bipartite Cubic Graphs)