Calendar

Below is the tentative schedule for the course. This calendar is subject to revision during the term. The section references only serve as a guide; your instructor may vary from it. Please make sure to check this page regularly for the most updated version.

• Lecture podcasts are available here: https://podcast.ucsd.edu/watch/fa19/math154_a00
• Schedule updated on October 20 to change the due date of HW 3 and 4
• Textbook has been updated on October 21 to fix a typo on page 59 on the definition of vertex and edge cover - LINK

Blank Slides/notes

Here are the blank slides that we shall use in this class. Please make sure to have them with you during lectures to follow along. This section will be updated throughout the course.

• Chapter 1 - Basic terminologies
• Chapter 2 - Eulerian and Hamiltonian graphs
• Chapter 3 & 4 - Trees & Connectivity
• Chapter 5 - Matching
• Chapter 6 - Graph coloring
• Chapter 7 - Planar graph
• Chapter 8 - Network flows

Week 0

Reading topics:

• Appendix and review the topic from Math 109 on sets, sequences, counting arguments (inclusion-exclusion & bijective counting), mathematical induction, and the pigeonhole principle.
• Chapter 1 - Intro to Graph Theory

Lecture notes:

• Day 01 - Friday 09/27 - Annotated notes

No discussion this week - Sections start next Thursday 10/03

No assignment due this week - Enjoy the welcoming activities!

Week 1

Reading topics:

• Chapter 1 - Intro to Graph Theory (cont.)
• Chapter 2 - Eulerian and Hamiltonian graphs (focus on the statement of the theorems during your pre-reading. We shall go over their proof in detail during lecture)

Lecture notes:

• Day 02 - Monday 09/30 - Annotated notes
• Day 03 - Wednesday 10/02 - Annotated notes
• Day 04 - Friday 10/04 - Annotated notes

HW 1 due Sunday 10/06 at 11:59pm

Week 2

Reading topics:

• Look up the following applications/algorithms:
  1. Dijkstra's algorithm for finding shortest path
  2. The Chinese Postman Problem (and how to construct an Eulerian tour/trail)
  3. The Traveling Salesman Problem
• Chapter 3 - focus on trees and properties of trees
• Look up the following applications/algorithms:
  1. Kruskal's algorithm on finding minimum spanning tree
  2. (Optional) Prim's algorithm

Lecture notes:

• Day 05 - Monday 10/07 - Annotated notes
• Day 06 - Wednesday 10/09 - Annotated notes
• Day 07 - Friday 10/11 - Annotated notes

No assignment due this week

Week 3

Reading topics:

• Chapter 3 - BFS and DFS (may skip Block Decomposition)
• Look up the following applications/algorithms:
  1. Kruskal's algorithm on finding minimum spanning tree
  2. (Optional) Prim's algorithm
• Chapter 4 - Menger's theorem (both forms)

Lecture notes:

• Day 08 - Monday 10/14 - Annotated notes
• Day 09 - Wednesday 10/16 - Annotated notes
• Day 10 - Friday 10/18 - Midterm 1 Review - Annotated notes

HW 2 due Saturday 10/19 at 11:59pm

Week 4

Reading topics:

• Chapter 5 - Matching (focus on cover, matching, Gallai's, Konig's and Hall's theorems)

Lecture notes:

• Midterm 1 - Monday 10/21, 9:00-9:50am in class
• Day 11 - Wednesday 10/23 - Annotated notes
• Day 12 - Friday 10/25 - Annotated notes

No assignment due this week

Week 5

Reading topics:

• Chapter 5 - cont. (focus on Konig-Ore's and Tuttle-Berge's formulas; Tutte's (1-factor) and Petersen's theorems)
• Look up the following applications/algorithms:
  1. The stable marriage problem and Gale-Shapley Algorithm
  2. The personnel assignment problem and Hungarian Algorithm
  3. Latin Squares
• Chapter 6 - Vertex Coloring and Brooks' Theorem

Lecture notes:

• Day 13 - Monday 10/28 - Annotated notes
• Day 14 - Wednesday 10/30 - Annotated notes
• Day 15 - Friday 11/01 - Annotated notes
• NOTES on the proof of Hall's Theorem
• NOTES on the proof of Tutte's Theorem

HW 3 due Sunday 11/03 at 11:59pm

Week 6

Reading topics:

• Chapter 6 - Edge Coloring - Konig's and Vizing's theorems
• Look up the following scheduling problems that can be solved with graph coloring:
  1. The Time Table Problem using edge coloring
  2. The Storage Problem using vertex coloring
  • Blank notes on Application of Coloring
• Chapter 7 - Planar Graphs (basic definitions and Euler's formula)

Lecture notes:

• Day 16 - Monday 11/04 - Annotated notes
• Day 17 - Wednesday 11/06 - Annotated notes
• Day 18 - Friday 11/08 - Annotated notes - Midterm 2 Theorems

No assignment due this week

Week 7

Reading topics:

• Chapter 7 - Coloring Planar Graphs; Contraction & Subdivision; Fary's theorem and Tutte-Whitney's theorem; Kuratowski's theorem

Lecture notes:

• Veterans Day - Monday 11/11 - no class
• Day 19 - Wednesday 11/13 - Annotated notes
• Day 20 - Friday 11/15 - Annotated notes

HW 4 due Saturday 11/16 at 11:59pm

Week 8

Reading topics:

• Chapter 7 - The Art Gallery Theorem
• Chapter 8 - Digraphs and networks
• Look up the Rotating Drum Problem and De Bruijn Sequences

Lecture notes:

• Midterm 2 - Monday 11/18, 9:00-9:50am in class
• Day 21 - Wednesday 11/20 - Blank note - Annotated notes
• Day 22 - Friday 11/22 - Blank note - Annotated notes

No assignment due this week

Week 9

Reading topics:

• Chapter 8 - Digraphs and networks
• Look up the Rotating Drum Problem and De Bruijn Sequences
• Chapter 8 - The Max-flow Min-cut algorithm (Ford-Fulkerson)

Lecture notes:

• Day 23 - Monday 11/25 - Annotated notes
• Day 24 - Wednesday 11/27 - Blank note - Annotated notes
• Thanksgiving Break - Friday 11/29 - no class

No assignment this week - enjoy your Thanksgiving break!

Week 10

Reading topics:

• Chapter 8 - The Max-flow Min-cut proof
• Reviews

Lecture notes:

• Day 25 - Monday 12/02 - Annotated notes
• Day 26 - Wednesday 12/04 - Annotated notes
• Day 27 - Friday 12/06 - Annotated notes
• Topic list for the Final Exam

HW 5 due Sunday 12/08 at 11:59pm

Week 11

Final Exam - Wednesday 12/11 from 8:00am to 11:00pm. Seat assignment will be up later on TritonED.