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, induced subgraphs.

Week 2

1.2, 1.3

Day 4: Characterization of bipartite graphs, Eulerian graphs.

Day 5: Vertex degrees, degree-sum formula, reconstruction conjecture.

Day 6: Extremal problems: largest minimum degree in disconnected graphs, largest bipartite subgraph, triangle-free graphs, etc.

Week 3

1.4, 2.1

Day 7: Degree sequences, graphic sequences, directed graphs.

X-hour: Quiz 1.

Day 8: Connected digraphs, Eulerian digraphs, De Bruijn cycles.

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

Week 4

2.2

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

Day 11: Counting spanning trees, deletion-contraction.

Day 12: 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).

X-hour: Quiz 2.

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, disconnecting sets, Whitney's theorem. 

Day 18: Blocks, k-connected graphs, Menger’s theorem.

Week 7

4.3, 5.1
 

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

X-hour: Quiz 3.

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

Day 21: Graph coloring.

Week 8

5.1, 5.3

Day 22: Bounds on chromatic numbers, chromatic numbers of graphs constructed from smaller graphs.

Day 23: The chromatic polynomial, the deletion-contraction recurrence.

Day 24: Properties of the chromatic polynomial, simplicial elimination orderings, acyclic orientations.

Week 9

Chapter 6

Day 25: Planar graphs, Euler's formula.

X-hour: Quiz 4.

Day 26: Kuratowski's theorem.

Day 27: Five and four color theorems.
Final exam handed out.

Week 10

Day 28: Graph theory and topology, by Doug Knowles.
Final exam due.