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

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