Course Syllabus

Sections

Brief Description

Week 1

1.1, 1.2

Day 1: 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.

Week 3

1.4, 2.1

Day 7: More extremal problems, degree sequences.

Day 8: Directed graphs, de Bruijn cycles.

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

Week 4

2.1, 2.2

Day 10: Spanning trees, radius and diameter.

Day 11: Midterm 1.

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

Week 5

2.2, 2.3, 3.1

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

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

Day 15: Matchings, maximal and maximum matchings, M-augmenting paths.

Week 6

3.1

Day 16: Hall's theorem and consequences.

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

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

Week 7

4.1, 4.2
 

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

Day 20: Midterm 2.

Day 21: Menger’s theorem, line graphs.

Week 8

4.3, 5.1

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

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

Day 24: Vertex colorings, bounds on chromatic numbers.

Week 9

5.3

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

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

Day 27: Planar graphs, Euler's formula.

Week 10

Chapter 6

Day 28: Kuratowski's theorem, five and four color theorems.