1 1/18We: introduction (overview of topics)

Chapter 6: Elementary Structural Concepts

2 1/20Fr: Matrix Tree background, Matrix Arborescence Theorem,
counting Eulerian circuits

3 1/23Mo: graceful labelings (hypercubes), T-decomposition (girth vs
diameter), intro to packing

4 1/25We: graph packing (Sauer-Spencer Thms, Bollobas-Eldridge Conj,
start of Hajnal-Szemeredi proof)

5 1/27Fr: completion of Hajnal-Szemeredi Theorem

6 1/30Mo: graphic and bigraphic lists (2-switch, Aigner-Triesch method)

7 2/01We: potentially k-edge-connected lists, Kundu's Theorem, vertex ptns
under degree constraints

8 2/03Fr: graph reconstruction (counting arguments, disconnected graphs,
tree preliminaries)

9 2/06Mo: reconstruction (trees, spanning subgraphs, almost all graphs),
edge-reconstruction

10 2/08We: product dimension (examples and bounds)

Chapter 7: Connection and Cycles

11 2/10Fr: connectivity of cartesian products, Edmonds' Branching Theorem

12 2/13Mo: Edmonds to Menger, Itai-Rodeh Conjecture, statement of
Lucchesi-Younger Theorem, *k*-linked graphs, forced subdivisions

13 2/15We: reminder of ear decomposition, contraction lemma & 3-connected
graphs (sketch of Tutte characterization), Halin example, *k*-valent
vertices in minimally *k*-connected graphs (Mader etc.)

14 2/17Fr: Gyori-Lovasz Theorem, gossip problem

15 2/20Mo: Nash-Williams Orientation Theorem, idea of Mader's average degree
*4k* guaranteeing *k*-connected subgraph

16 2/22We: toughness (9/4-tough non-Hamiltonian), *k*-closure,

17 2/24Fr: density conditions (Bondy-Chvatal condition for *t*
dominating verts, Las Vergnas condition), Lu's Theorem strengthening
Chvatal-Erdos

18 2/27Mo: circumference (Erdos-Gallai Thm, Bondy's Lemma on long paths,
long-cycle version of Ore's Theorem, Fan's Theorem), digraphs skipped
(Ghoula-Houri, Meyniel)

19 2/29We: stronger conclusions (Thomason lollipop, Fink on hypercubes,
Bondy pancyclicity)

20 3/02Fr: Jackson's Theorem (regular graphs),
claw-free graphs skipped (Matthews-Sumner Conjecture, Ryjacek closure)

Chapter 8: Planar and non-planar graphs

21 3/05Mo: MacLane/Whitney planarity criteria, Schnyder labeling & grid
embedding (overview)

22 3/07We: Schnyder labelings (proofs)

23 3/09Fr: Reducibility of Birkhoff diamond, discharging technique
(Franklin, Cranston edge-choosability, skipped Borodin's light triangles)

24 3/12Mo: dynamic coloring by discharging, Tait's and Grinberg's Theorems
and Hamiltonicity in planar graphs (brief mention)

25 3/14We: Grotzsch's Theorem, Steinberg's Conjecture
(Borodin-Sanders-Zhao), brief mention of Jaeger's Conjecture (circular coloring
of planar graphs with large girth)

26 3/16Fr: Lipton-Tarjan Separator Theorem, skipped applications

27 3/26Mo: #perfect matchings in planar bipartite graphs (Kasteleyn),
start interval number

28 3/28We: interval number and total interval number of planar graphs,
thickness

29 3/30Fr: outerplanar thickness, pagenumber, start of crossing number

30 4/02Mo: crossing number and application, *t*-linear crossing
numbers

31 4/04We: genus, Heawood's Formula

32 4/06Fr: rotation schemes and voltage graphs

Chapter 9: Graph minors and related topics

33 4/09Mo: graph minors, testing minors, *K _{4}*-minor-free
= 2-decomposable

34 4/11We: treewidth characterizations, cops-and-robber

35 4/13Fr: brambles, min/max for treewidth

36 4/16Mo: approach to graph minor theorem, well-quasi-ordering for trees

37 4/18We: cycle covers and flows

38 4/20Fr: flows on surfaces, 8-flow theorem

39 4/23Mo: modular flows, 6-flow theorem

Chapter 10: Algebraic aspects of graphs

40 4/25We: eigenvalues (basics, bipartite graphs, diameter)

41 4/26Th: interlacing, bounds on largest eigenvalue, eigenvalues of
regular graphs

42 4/30Mo: strongly regular graphs (Moore graphs, Friendship Theorem)

43 5/02We: Laplacian eigenvalues (algebraic connectivity, spanning trees,
expansion properties)