Syllabus (being updated as the course proceeds):
Module-0: Perfect Matchings and Matchable Graphs (1 week)
Perfect Matchings & Matchable Graphs
Tutte's Theorem characterizing Matchable Graphs (and its proof due to Tutte & Lovasz)
Petersen's Theorem
Hall's Theorem (as a consequence of Tutte's Theorem)
Module-1: Matching Covered Graphs (MCGs), Barriers and Tight Cuts (3 weeks)
Barriers & the Core of a Matchable Graph (with respect to a barrier)
The Kotzig Relation
Matchable Edges, MCGs & Bicritical Graphs (and their characterizations in terms of barriers)
The Dulmage-Mendelsohn Decomposition for Bipartite Matchable Graphs
A strengthening of Petersen's Theorem
Some important infinite families of MCGs
Operations for constructing MCGs: Bi-subdivisions & Splicing
The (Kotzig-Lovasz) Canonical Partition Theorem & the Canonical Partition of a MCG (& its proof using the Core)
Odd Cuts, Separating Cuts and Tight Cuts
Barrier Cuts and 2-separation Cuts
The Tight Cut Decomposition Procedure, and Bricks & Braces
Crossing versus Laminar Cuts, and Laminar Families of (Tight) Cuts
The Uncrossing Lemma for Tight Cuts
Lovasz's Unique (Tight Cut) Decomposition Theorem (and its proof due to Lovasz)
Tight Cuts in Bipartite MCGs, and Braces (and their characterizations)
The ELP (Edmonds, Lovasz & Pulleyblank) Theorem (and its brief history)
Peripheral Tight Cuts, and Dulmage-Mendelsohn barriers (DM-barriers)
Proof of the ELP Theorem using DM-barriers (due to Carvalho, Lucchesi and Murty; inspired by Szigeti's proof)
An application of the ELP Theorem: Characterizing Tight Cuts in Cubic MCGs
Essentially 4-edge-connected graphs & cubic graphs
The Laminar ELP Theorem (only statement)
Bi-contraction, bi-splitting, retracts and 2-stable retracts
Module-4.1: Pfaffian Orientations (2 weeks)
Skew-Symmetric Matrices (SSMs) and their Pfaffians
Correspondence between SSMs and Weighted Digraphs
Cayley's Theorem (only statement)
Sign of a Perfect Matching (w.r.t. an orientation)
Counting the Number of PMs using Pfaffian Orientations (POs)
Valiant's Theorem (only statement)
Pfaffian Digraphs, Orientations & Graphs
Two Decision Problems: Pfaffian Recognition Problem (PRP) & Pfaffian Orientation Problem (POP)
Oddly-oriented and evenly-oriented trails (with focus on cycles)
POs of even cycles; Comparing the signs of two PMs
Conformal subgraphs and cycles
Equivalent definitions of POs using conformal cycles and M-alternating cycles
K_{3,3} is NOT Pfaffian --- proof and ideas
Intractable Collection of Conformal Cycles; Little's Theorem (only statement)
Kasteleyn's Theorem (planar implies Pfaffian)
Similarity of Orientations, and POs under similarity
POs versus Separating Cuts
POs versus Tight Cuts: reducing the POP to bricks & braces
Module-2: Removability, Dependence and Ear Decompositions
Revisiting the Ear Decomposition Theorem for Bipartite MCGs
Conformal Subgraphs & Cycles
An easy (but not very useful) "ear decomposition theorem" for all MCGs
Two different viewpoints: adding ears versus deleting ears
Removable Ears
The Lovasz-Plummer Two Ear Theorem
Dependence, Mutual Dependence & Removability
Dependence Digraph & Reduced Dependence Digraph
Source classes of cardinality one and two
Even 2-cuts versus Source classes of cardinality two or more
Removable classes: edges & doubletons
Proof of the Lovasz-Plummer Two Ear Theorem
Conformal Minors
Lovasz's Primary Ear Decomposition Theorem
Dependence Classes in Bricks
Near-Bipartite Graphs versus Near-Bricks