Graph Theory, Lectures

The PDF lecture notes are available freely. Here is a sample of one of the lectures with animation and audio.

UNM, Spring '002,ProfessorTerry A. Loring

Lectures

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.

Current Week

Week 1

#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.

Week 2

#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.

Week 3

#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.

Week 4

#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.

Week 5

#12, Monday, 2/11/2002: Traffic flow. More animations of the Petersen graph.
#13, Wednesday, 2/13/2002: Review.
Friday, 2/15, Midterm.
Reading: §3.5.

Week 6

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.

Week 7

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.

Week 8

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.

Week 9

Monday, 3/18/2002: Weighted digraphs. Minimal cost paths.
Wednesday, 3/20/2002: Digraphs with real weights. Longest paths.
Friday, 3/22/2002: Counting walks. Matrix multiplication. Longest paths.
Reading: §8.1, 8.2, 8.3.
Homework: Assigned Wednesday (due next Friday).

Week 10

Monday, 3/27/2002: The Rotating Drum Problem. A Maze.
Wednesday, 3/29/2002: Review for Fridays Test.
Reading:
Homework:

Week 11

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.

Week 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.
Homework:

Week 13

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.

Week 14

Monday, 4/22: M0re about dual graphs. Coloring maps and graphs.
Wednesday, 4/24/2002: Chromatic polynomials.
Friday, 4/26/2002: Factoring coloring counts by symmetries.
Reading: 12.1, 12.2
Homework:

Week 15

Monday, 4/29/2002: Computing Chromatic Polynomials.
Wednesday, 5/1/2002: Review.
Friday, 5/3/2002: Pre-recorded solutions to the problems posed Wednesday. No audio,

Graph Theory Lectures

Lectures

Current Week

Week 1

Week 2

Week 3

Week 4

Week 5

Week 6

Week 7

Week 8
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.

Week 9

Week 10

Week 11

Week 12

Week 13

Week 14

Week 15

Graph Theory Lectures

Lectures

Current Week

Week 1

Week 2

Week 3

Week 4

Week 5

Week 6

Week 7

Week 8 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.

Week 9

Week 10

Week 11

Week 12

Week 13

Week 14

Week 15

Week 8
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.