Discrete Mathematics and Graph Theory
Math 154 - Winter 2025
| Place and Time: | Peterson Hall 104, TTh 9:30am-10:50am |
| Instructor: | Daniel Grier (dgrier@ucsd.edu) |
| Resources: | Canvas, Gradescope, Piazza, Textbook |
| TAs: | Bryan Hu (brhu@ucsd.edu), Yunseong Jung (y8jung@ucsd.edu) |
| Discussion: |
A01: APM 5402, F 2:00pm-2:50pm, Bryan Hu A02: APM 5402, F 3:00pm-3:50pm, Bryan Hu A03: CENTR 217B, F 5:00pm-5:50pm, Yunseong Jung |
| Daniel's office hours: | Thursday after class and by appointment in APM 7141 |
| Bryan's office hours: | Fridays at 4pm in HSS 5012 |
| Yunseong's office hours: | Mondays at 11am in APM 5801 |
Assignments
- Homework 1 - due January 13th at 11:59pm
- Homework 2 - due January 21st at 11:59pm
| Lecture 1 | Introduction to graphs | 1.1, 1.4-1.6 |
| Lecture 2 | Graph isomorphisms, combinatorics, and subgraphs | 1.3, 1.7, A.2-A.3 |
| Lecture 3 | Walks, connectedness, and Eulerian tours | 2.1-2.3 |
| Lecture 4 | De Bruijn sequences, Hamiltonian paths/cycles | 2.4-2.6 |
Overview
Basic concepts in graph theory, including trees, walks, paths, and connectivity, cycles, matching theory, vertex and edge-coloring, planar graphs, flows and combinatorial algorithms, covering Hall’s theorems, the max-flow min-cut theorem, Euler’s formula, and the travelling salesman problem.
Textbook: Introduction to Graph Theory, Jacques Verstraete (requires access to Canvas)
Prerequisites: Math 31CH or Math 109
Evaluation
- Homework (30%): There will be 6-7 homework assignments throughout the quarter. The lowest homework grade will be dropped. You are allowed to turn homeworks assignments in 1-day late for a 25% penalty. No other late submissions will be accepted.
- Participation (10%): Participation is based entirely on online quizzes on Gradescope given both synchronously and asynchronously. Your lowest 3 quiz scores will be dropped.
- Midterm (25%): Date - Feb 6th in class. There is no make-up midterm.
- Final (35%): Date - Mar 18th at 8am during finals week. If final grade is higher than midterm, it will replace the midterm grade.
Accommodations
Students requesting accommodations for this course due to a disability must provide a current Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities. Students are required to discuss accommodation arrangements with instructors and OSD liaisons in the department in advance of any exams or assignments.