Math 154: Discrete Mathematics and Graph Theory
Winter 2020, Prof. Tesler
This is a one-quarter introduction to basic concepts in graph theory. Topics include trees, walks, paths, and connectivity, cycles, matching theory, vertex and edge-coloring, planar graphs, flows and combinatorial algorithms, Hall's theorem, the max-flow min-cut theorem, Euler's formula, and the travelling salesman problem.
Introduction to Graph Theory
by Prof. Jacques Verstaete (UCSD Department of Mathematics).
Download it from the front page of this class website.
It may be revised during the course; please make sure you have the latest version.
Lectures may be on the chalkboard or on slides.
For lectures with slides, the slides will be posted on
the Calendar page of the class website.
You may want to print the slides in advance, 4 or 6 per sheet, to facilitate note-taking.
Weekly homework, one midterm, one final.
Your composite grade is comprised of homework (30% for all homeworks
combined), the midterm (30%), and the final (40%).
Homework: Homework assignments
will be posted on the class website
and are due Fridays at 1 p.m. (unless otherwise noted). You may turn them in
at discussion section or at your T.A.'s homework box
located in the basement of AP&M (from the AP&M lobby,
go down the stairs one floor and take a left for the homework boxes).
Graded homework will be handed back in discussion sections.
Please write your name, student ID number,
date, section number (A01-A03),
and assignment number at the top of the first page.
- Show your work, and when relevant, circle your final answer.
- Please present your solutions in the order the problems are listed.
- On proof-oriented problems, you need to write a coherent proof.
- Certain problems will be selected for detailed grading. The remaining problems that are not graded in detail will count towards completeness points. You need to do all assigned problems, including any with full or partial solutions in the book.
Please staple the pages together. If you turn in loose pages,
fold pages together, tear and twist the corners, use paper clips, etc.,
your pages will probably be separated or snagged into someone else's
assignment, and you will not receive credit.
You may study with others currently enrolled in the class, but the work you turn in should be your own;
do not just copy someone else's answer.
That includes that you should not copy from an answer manual, answer key, or the internet.
You are strongly advised to attend section.
Late homeworks will not be accepted.
Your lowest homework score (including 0 for not turning in an assignment)
will be dropped.
Exams: There will be one midterm
(Friday February 7, in class) and one final (Wednesday March 18, 3-6 p.m.).
They will be
comprehensive. Rules and material covered on each exam will be
announced the prior week.
No make up exams will be given.
Lectures and discussion sections:
Attending lectures and discussion sections
is a fundamental part of the course.
You are responsible for all of the material presented
whether or not it is discussed in the textbook or slides.
Students with special needs or disabilities must provide the instructor with an Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities (OSD) in the first week of class, or as soon as possible if the situation arises later.
Arrangements for UCSD Athletics teams, documented medical emergencies, etc., must be requested with appropriate documentation as soon as possible.
Cheating will not be tolerated. See the
UCSD Policy on Integrity of Scholarship.