1 1/14Mo: introduction (overview of topics)

Chapter 6: Elementary Structural Concepts

2 1/16We: Matrix Tree background, Matrix Arborescence Theorem,
counting Eulerian circuits

3 1/18Fr: graceful labelings (hypercubes), T-decomposition (girth vs diameter)

4 1/23We: graph packing (Sauer-Spencer Thms, Bollobas-Eldridge Conj)

5 1/25Fr: Hajnal-Szemeredi Theorem (new proof)

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

7 1/30We: potentially k-edge-connected lists, vertex ptns under maximum
or minimum degree constraints

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

9 2/04Mo: reconstruction (trees, almost all graphs), edge-reconstruction

10 2/06We: isometric embedding & metric representation

11 2/08Fr: product dimension

Chapter 7: Connection and Cycles

12 2/11Mo: Edmonds' Branching Theorem and applications, sketch of
Lucchesi-Younger Theorem

13 2/13We: *k*-linked graphs, forced subdivisions

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

15 2/18Mo: Gyori-Lovasz Theorem, proof for gossip theorem

16 2/20We: Nash-Williams Orientation Theorem

17 2/22Fr: toughness (9/4-tough non-Hamiltonian), *k*-closure, density
conditions (Bondy-Chvatal condition for *t* dominating verts,
Las Vergnas condition)

18 2/25Mo: Lu's Theorem strengthening Chvatal-Erdos (skipping hard case)

19 2/27We: Hamiltonian claw-free graphs (Matthews-Sumner Conjecture,
Ryjacek closure)

20 2/29Fr: circumference (Erdos-Gallai Thm, Bondy's Lemma on long paths,
Bermond's Theorem, Fan's Theorem), digraphs skipped (Ghoula-Houri, Meyniel)

Chapter 8: Planar and non-planar graphs

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

22 3/05We: Schnyder labelings (proofs)

23 3/07Fr: Reducibility of Birkhoff diamond, discharging technique
(Wernicke, Borodin's light triangles)

Note: skipped Tait's and Grinberg's Theorems and Hamiltonicity in planar
graphs

24 3/10Mo: Grotzsch's Theorem, Thomassen 3-colorability of planar graphs
with girth at least 5

25 3/12We: Jaeger's Conjecture (circular coloring of planar graphs with
large girth)

26 3/14Fr: Lipton-Tarjan Separator Theorem, sketch of application to
independent sets (skipped pebbling)

27 3/24Mo: counting perfect matchings in planar bipartite graphs (Kasteleyn)

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

29 3/27Th: thickness and pagenumber

30 3/31Mo: crossing number and application

31 4/02We: *t*-linear crossing numbers, genus, Heawood's Formula

32 4/04Fr: voltage graphs

Chapter 9: Graph minors and related topics

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

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

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

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

37 4/16We: cycle covers and flows

38 4/18Fr: 8-flow theorem

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

Chapter 10: Algebraic aspects of graphs

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

41 4/25Fr: interlacing, bounds on largest eigenvalue, eigenvalues of
regular graphs

42 4/28Mo: eigenvalues and expanders, strongly regular graphs (Friendship Theorem)

43 4/30We: chromatic polynomial, with relation to rank and Tutte
polynomials