Graph Theory Lectures
The PDF lecture notes are available freely. Here is
of one of the lectures with animation
The descriptions of the lectures below
are only help you identify the lecture you seek.They may fail
to mention important topics. I strongly advise all students
to print the complete set of PDF notes as we go along.
- #1, Monday, 1/14/2002: Graphs as abstract connection diagrams.
- #2, Wednesday, 1/16/2002: Graphs defined using sets and list.
The utilities problem. Loops, multiple edges, simple graphs, defined.
- #3, Friday, 1/18/2002: Degree of a vertex,
regular graph, even and odd vertex, defined. Degree sequences. The handshake lemma.
- Reading: §1.1, §1.2, §1.3 .
- Homework: Assigned during Wednesday's lecture.
Due Wednesday 1/23.
- #4, Wednesday, 1/23/2002: Isomorphism.
- #5, Friday, 1/25/2002: We worked on counting the number of simple graphs with three or four vertices.
- Reading: §1.4, §1.5, §1.6.
- Homework: Assigned during Friday's lecture. Due Friday 2/1.
- #6, Monday, 1/28/2002:
Adjacency matricies and how they relates to isomorphism. Incidence matrices.
- #7, Wednesday, 1/30: Walks, Trails, Paths. Bipartite graphs.
- #8, Friday, 2/1: Cube graphs. The Petersen graph. A generalized Petersen graph. Trees. Cycles.
- Reading: §2.1, 2.2, 2.3.
- Homework: Assigned during Friday's lecture. Due Friday 2/8.
- #9, Monday, 2/4: A little chemistry. Isomers of C_10H_4.
- #10, Wednesday, 2/6: A little Trade Politics. Rooted trees. Balanced and unbalanced weighted graphs.
- #11, Friday, 2/8: An animation of the Petersen graph. Bracing rectangular framework.
- Reading: §3.1, 3.2, 3.3, 3.4.
- Homework: Assigned during Friday's lecture. Due Monday 2/18.
- Monday, 2/18/2002: No lecture, instructor ill.
- #14, Wednesday, 2/20/2002:
Directed graphs. Animations of flexing systems of beams and of traffic lights.
- Friday, 2/22: No lecture, instructor ill.
- Reading: §4.1, 4.2.
- Homework: none.
- Monday, 2/25: Orientability. Bridges. Adjacency and Incidence matrices for digraphs. Terrible audio--instructor still ill.
- Wednesday, 2/29/2002:
Orientability and Bridges, finished. Counting digraphs. Why in-degree and out-degree sequences aren't always useful.
- Friday, 3/1: Finite State Automata: an application of digraphs to parsers of low-level languages. All students should catch the short addendum to the lecture (in flash).
- Reading: §4.3, 4.4, 5.2. (The rest of chapter 5 we'll skip.)
- Homework: Assigned during Monday's lecture.
- Monday, 3/5: Euler circuits. Strong Mathematical Induction.
- Wednesday, 3/7: A proof of the Euler Ciruit Theorem.
- Friday, 3/9: Another proof of the Euler Ciruit Theorem. Euler walks (edge traceable graphs).
- Reading: Appendix on Proofs (p112), §6.1, 6.2, 6.3.
- Homework: none.
- Monday, 4/1/2002: Accesibility of vertices in a graph. (Uses some linearalgebra. This topic is not in the book.
- Wednesday, 4/3: Degrees of connectedness. Cut-sets and vertex-cut-sets.
- No lecture. Instructor ill.
- Reading: §9.1, 9.2, 9.3
- Homework: Assigned during Wednesday's lecture, but due Friday, April 12.
- Monday, 4/8: Menger's Theorem, and the book's "proof."
- Wednesday, 4/10: Menger's Theorem, with proof.
- Friday, 4/12: Planar graphs. Euler's theorem. Graphs drawn on Klein bottles.
- Reading: 9.4, 9.5, 11.1, 11.2.
- Monday, 4/15: Building graphs from basic parts.
- Wednesday, 4/17/2002: Euler's Theorem.
- Friday, 4/19/2002: Dual graphs. (Impractical) test for planarity. Contracting an edge. Subdivision.
- Reading: 11.3, 11.4, 11.5
- Homework: In Wednesday's lecture.