Schedule for Math 104
| Lecture | Material | Related reading |
|
Lec 1 (01/22) |
Course introduction
Graph theory warmup (notation, subgraphs, complements, equal vs. isomorphic) Graph theory fundamentals (isomorphisms and automorphisms, def'ns of bipartite and complete multipartite graphs) |
1.1 |
|
Lec 2 (01/24) |
Graph theory fundamentals, cont. (matrices of graph, degree-sum formula, walks/paths/cycles, connected graph, components, cut edge/vertex) | 1.1, 1.2 (to pg 26), 1.3 (to pg 36) |
|
Lec 3 (01/29) |
Graph theory fundamentals, cont.
(bipartite graph characterization, induction trap)
Trees (leaves, properties) Slides (viewing) Slides (printing) |
1.2 (to pg 26), 2.1 |
|
Lec 4 (01/31) |
Trees, cont. (characterizations, spanning trees)
Counting spanning trees |
2.2 (to pg 87) |
|
Lec 5 (02/05) |
Counting spanning trees
(deletion/contraction, matrix-tree thm, Cayley's thm) Minimum spanning trees (weighted graphs, greedy algorithms, Kruskal's algorithm) |
2.2 (to pg 87), 2.3 (to pg 97) |
|
Lec 6 (02/07) |
Matchings
(def'n, saturated vtcs, augmenting paths, Berge's thm) Matchings in bipartite graphs (Hall's theorem, Hall's marriage theorem) |
3.1 (to pg 115) |
|
Lec 7 (02/12) |
Vertex covers
(def'n, examples, relationship to matchings) Important graph invariants (α(G), β(G), α'(G), β'(G), Konig-Egervary thm) |
3.1 (to pg 115) |
|
Lec 8 (02/14) |
Matchings in general graphs (odd components, Tutte's thm) | 3.3 |
| Lec 9 (02/19) |
Connectivity and cuts
(vertex/edge connectivity, cut sets, edge cuts, Whitney's inequality)
Slides (viewing) Slides (printing) |
4.1 |
|
Lec 10 (02/21) |
Menger's theorems and network flows
(digraphs, networks, flows, s-t cuts, max flows, min cuts, Ford-Fulkerson algorithm)
Slides (viewing) Slides (printing) |
1.4, 4.2, 4.3 |
|
Lec 11 (02/26) |
Menger's theorems
(formulation of Menger's thms as network flow problems) Vertex coloring (chromatic number, bounds, k-critical graphs) Slides (viewing) Slides (printing) |
4.2, 4.3, 5.1 |
|
Lec 12 (02/28) |
Vertex coloring, cont.
(k-critical graphs, greedy coloring, Brooks' thm) Slides (viewing) Slides (printing) |
5.1 |
|
Lec 13 (03/07) |
Mycielski's construction Chromatic polynomials |
5.2, 5.3 |
|
Lec 14 (03/12) |
Chromatic polynomials, cont. Combinatorial reciprocity |
5.3 |
|
Lec 15 (03/14) |
Edge coloring
Line graphs |
7.1 |
|
Lec 16 (03/26) |
Planarity: introduction (Jordan curve theorem, Euler's formula) | 6.1-6.2 |
|
Lec 17 (03/28) |
Planarity: characterizations and
special classes of planar graphs (duals, subdivisions, minors, maximal planar graphs) Slides (viewing) Slides (printing) |
6.1-6.2 |
|
Lec 18 (04/02) |
Planarity: coloring and surfaces of
higher genus
Slides (viewing) Slides (printing) |
6.3 |
|
Lec 19 (04/09) |
Planarity: coloring and surfaces of
higher genus, cont. Hamiltonian graphs Slides (viewing) Slides (printing) |
6.3, 7.2 |
|
Lec 20 (04/11) |
Hamiltonian graphs, cont. Long paths in digraphs and tournaments |
7.2, 5.1 (pgs 196-197), 1.4 (pgs 62-63) |
|
Lec 21 (04/16) |
Long paths in digraphs and
tournaments, cont. Ramsey theory |
5.1 (pgs 196-197), 1.4 (pgs 62-63) 8.3 |
|
Lec 22 (04/18) |
Ramsey theory, cont. | 8.3 |
|
Lec 23 (04/23) |
A taste of perfect graphs | |
|
Lec 24 (04/25) |
Perfect graphs, cont. Chordal graphs |
|
|
Lec 25 (04/30) |
Chordal graphs, cont. A peek at the probabilistic method Slides (viewing) Slides (printing) |
|
|
Lec 26 (05/02) |
Open problems in graph theory |
