Course Syllabus

Sections

Brief Description

Week 1

1.1, 1.2

Day 1: Basic definitions, examples of problems in graph theory.

Day 2: Adjacency and incidence matrices, isomorphisms.

Day 3: Paths, walks, cycles, components, cut-edges, cut-vertices.

Week 2

1.2, 1.3

Day 4: Bipartite graphs, Eulerian graphs.

Day 5: Vertex degrees, reconstruction conjecture.

Day 6: Extremal problems, degree sequences.

Week 3

1.4, 2.1

Day 7: Directed graphs, de Bruijn cycles.

Day 8: Orientations and tournaments. Trees and forests, characterizations of trees.

Day 9: Radius and diameter. Spanning trees.

Week 4

2.2

Day 10: Enumeration of trees, Cayley’s formula, Prüfer code.

Day 11: Midterm 1.

Day 12: Counting spanning trees, deletion-contraction, the matrix tree theorem, graceful labelings.

Week 5

2.3, 3.1

Day 13: Minimum spanning trees (Kruskal’s algorithm), shortest paths (Dijkstra’s algorithm).

Day 14: Matchings, maximal and maximum matchings, M-augmenting paths. Hall's theorem and consequences.

Day 15: Min-max theorems, maximum matchings and vertex covers, independent sets and edge covers.

Week 6

3.1, 4.1, 4.2

Day 16: Independent sets and edge covers (continued). Connectivity, vertex cuts.

Day 17: Edge-connectivity, blocks, k-connected graphs.

Day 18: Menger’s theorem, line graphs.

Week 7

4.3
 

Day 19: Network flow problems, flows and source/sink cuts.

Day 20: Midterm 2.

Day 21: Ford-Fulkerson algorithm, Max-flow min-cut theorem. 

Week 8

5.1, 5.3

Day 22: Vertex colorings, bounds on chromatic numbers.

Day 23: Chromatic numbers of graphs constructed from smaller graphs, chromatic polynomials.

Day 24: Properties of the chromatic polynomial, the deletion-contraction recurrence.

Week 9

Chapter 6

Day 25: Planar graphs, Euler's formula.

Day 26: Kuratowski's theorem.

Day 27: Five and four color theorems.