• Syllabus

• Calendar
  (Note that this calendar is potentially subject to revision, depending on the needs of the class)

• Lecture 1: Motivation, basic definitions

• Lecture 2: A few more definitions, graph representations, graph isomorphisms

• Lecture 3: Graph isomorphisms, walks, trails, paths

• Lecture 4: Walks, trails, paths, Degree-Sum Formula, additional definitions

• Lecture 5: Characterization of bipartite graphs, König's Theorem, Eulerian circuits, Euler's Theorem

• Lecture 6: Euler's Theorem, Mantel's Theorem, degree sequences

• Lecture 7: Graphic degree sequences, Havel-Hakimi algorithm, examples and non-examples

• Lecture 8: Basic definitions for directed graphs (digraphs), Degree-Sum Formula for digraphs, connectedness (weak and strong), Euler's Theorem for digraphs

• Lecture 9: de Bruijn graphs, tournaments, kings

• Lecture 10: Trees, forests, a characterization theorem for trees

• Lecture 11: Characterization theorem for trees, distance, eccentricity, diameter, radius, center, Jordan's theorem on centers of trees

• Lecture 12: Prüfer code, Prüfer algorithm, properties of Prüfer codes, Cayley's Formula

• Lecture 13: Spanning trees, edge contraction, Matrix-Tree Theorem

• Lecture 14: Kruskal's algorithm, Prim's algorithm (+ bonus Dijkstra's algorithm)

• Lecture 15: Matchings, perfect matchings, maximum matchings, M-alternating paths, M-augmenting paths

• Lecture 16: Hall's Theorem, Marriage Theorem, vertex covers

• Lecture 17: Vertex covers, König-Egerváry Theorem, min-max relations, edge covers

• Lecture 18: Edge covers, Gallai's Theorem (+corollary), stable matchings, Gale-Shapley algorithm

• Lecture 19: Proof of Gale-Shapley algorithm, factors, odd components, Tutte's Theorem (and the first portion of the proof)

• Lecture 20: Tutte's Theorem (second portion of proof), cut edges

• Lecture 21: Cut vertices, Berge-Tutte Formula, Corollaries to Tutte's Theorem

• Lecture 22: Petersen's 2-factor theorem, connectivity, separating sets, k-connected graphs

• Lecture 23: Edge-connectivity and relationships between connectivity, edge-connectivity, and minimum degree

• Lecture 24: End of Theorem 4.3, internally disjoint paths, Whitney's theorem on 2-connected graphs

• Lecture 25: Expansion Lemma, Characterization theorem for 2-connected graphs

• Lecture 26: Subdivision of 2-connected graphs, ear decompositions, characterization of 2-connected graphs in terms of ear decompositions

• Lecture 27: x,y-cuts, statement and first portion of proof for Menger's Theorem for vertex connectivity

• Lecture 28: Majority of the proof for Menger's Theorem for vertex connectivity, impact of edge deletion on connectivity

• Lecture 29: Other versions of Menger's Theorem (global connectivity, local edge-connectivity, digraphs), basic network definitions

• Lecture 30: Networks, flows (positive, feasible, circulations), circulations as sums of flows along cycles

• Lecture 31: Positive flows as sums of flows along cycles, s,t-paths, and t,s-paths, maximum flows, f-augmenting paths

• Lecture 32: s,t-cuts and their capacities, an upper bound on the maximum flow in a network, Ford-Fulkerson algorithm, statement of the Max-Flow Min-Cut Theorem

• Lecture 33: Proof of Max-Flow Min-Cut Theorem, maximum matchings in bipartite graphs via network flows, proof of Menger's Theorem for digraphs

• Lecture 34: Definitions and examples of planar and plane graphs, the Restricted Jordan Curve Theorem, Euler's Formula

• Lecture 35: Bound(s) on the number of edges in a planar graph, non-planarity of K5 and K3,3, statement of Kuratowski's Theorem, graph subdivisions and minors, maximal planar graphs, triangulations, outerplane and outerplanar graphs

• Lecture 36: A necessary and sufficient condition for outerplanarity, basic definitions and examples for graph coloring, chromatic number, k-critical graphs, greedy coloring, an upper bound on chromatic number is 1 + maximum vertex degree

• Lecture 37: Other bounds for chromatic number, blocks and leaf blocks, statement and beginning of the proof of Brooks' Theorem

• Lecture 38: Majority of the proof of Brooks' Theorem, Mycielski's Construction of triangle-free graphs with arbitrarily high chromatic number, statement of Mycielski's Theorem

• Lecture 39: Proof of Mycielski's Theorem, basic definitions and examples for edge-coloring, chromatic index, line graphs

• Lecture 40: Several bounds on chromatic index, statement of König's theorem about the chromatic index of bipartite graphs, Shannon's Theorem

• Lecture 41: Vertex-connectivity, edge-connectivity, Whitney's Theorem

As mentioned in the syllabus, I highly encourage typesetting assignments rather than writing by hand. You may wish to do so using Overleaf, which is free and cloud-based. If you would find it helpful, I have created a basic template for homework in this course (the TeX code is available here). You are not required to use this template.

• Homework 1: PDF, TeX, Solutions
  Optional (but suggested) practice problems: PDF

• Homework 2: PDF, TeX, Solutions
  Optional (but suggested) practice problems: PDF

• Homework 3: PDF, TeX, Solutions
  Optional (but suggested) practice problems: PDF

• Homework 4: PDF, TeX, Solutions
  Optional (but suggested) practice problems: PDF

• Homework 5: PDF, TeX, Solutions
  Optional (but suggested) practice problems: PDF

• Homework 6: PDF, TeX, Solutions
  Optional (but suggested) practice problems: PDF

• Homework 7: PDF, TeX, Solutions
  Optional (but suggested) practice problems: PDF

• Homework 8: PDF, TeX, Solutions
  Optional (but suggested) practice problems: PDF

• Homework 9: PDF, TeX, Solutions

• Homework 10: PDF, TeX, Solutions
  Optional (but suggested) practice problems: PDF

• "Guidelines for good mathematical writing," by Francis Su.

• Detexify, a web app for identifying the LaTeX command(s) for various symbols.

• Overleaf, a cloud-based LaTeX editor.

• GraTeX, a free tool for generating TikZ code for graphs.