MAT 332, Introduction to Graph Theory, Fall 2022

Instructor

Prof. Kasra Rafi
Office: BA 6236 (Bahen Centre)
Email: rafi@math.toronto.edu

Meetings

Tuesdays 1-3 pm in SS 2108.
Thursdays 2-3 pm in SS 2108.

Office Hours

Tuesdays 12-1 pm, Thursdays 1-2 pm or by appointment.

Teaching Assistants

Vivian He
Email: vivian.he@mail.utoronto.ca

Kunal Chawla
Email: kunal.chawla@mail.utoronto.ca

Textbook

Introduction to Graph Theory, 2nd Edition, by Douglas B. West.

Course Description

This course is an introduction to Graph Theory. The topics covered include: Graphs, subgraphs, isomorphism, trees, connectivity, Euler and Hamiltonian properties, matchings, vertex and edge colourings, planarity, network flows and strongly regular graphs.

Prerequisites

MAT 224H1 / MAT 247H1.

You need to be comfortable with proofs and with using the language of set theory, like defining a set, function, relation, etc. Familiarity with Linear Algebra, elementary number theory and modular arithmetic is also useful for some of the examples we will discuss.

Exams

There will be one midterm and one final exam.

The midterm will take place on Tuesday, October 18, 1-3 pm in SS 2108. See the Midterm Guide for the list of topics that will be covered and the Past Midterm from 2017.

The final exam will take place on Tuesday, December 13, 7-10 pm in HA 403. See the Final Guide for the list of topics that will be covered and the Past Final Exam from 2017.

Homework and Quizzes

There will be weekly homework assignments. However the homework will not be collected. Instead, there will be weekly quizzes based on the homework problems. Two quizzes with the lowest grades will be dropped from the final calculation to accomodate students missing class due to illness or emergencies. Students are encouraged to work together on the homework problems.

Homework Problems

• Due September 13
  1. Read Appendix A and Chapter 1.1
  2. Chapter 1.1: 4, 5, 7, 11, 14, 18, 22, 24, 27, 29, 31, 34
• Due September 20
  1. Read Chapter 1.2
  2. Chapter 1.2: 1, 3, 10, 12, 16, 18, 20, 22, 25, 28, 40
Due September 27
1. Read Chapter 1.3
2. Chapter 1.3: 1, 2, 4, 7, 13, 18, 26, 31, 36, 41, 44, 47, 64
• Due October 4
  1. Chapter 1.4: 3, 4, 7, 8, 12, 14, 20, 22, 29, 36
• Due October 11
  1. Chapter 2.1: 2, 4, 7, 12, 14, 16, 24, 36, 37, 49
  2. Chapter 2.2: 7, 8, 9
• Due Oct 18
  1. Chapter 3.1: 1, 3, 8, 10, 11, 18, 21, 26, 30, 42
• Due Oct 25
  1. Chapter 4.1: 1, 5, 8, 10, 12, 14, 18
• Due November 1
  1. Chapter 4.1: 2, 15, 24, 25, 28, 30, 32
  2. Chapter 4.2: 1, 2, 4, 6, 10
• Due Nov 22
  1. Chapter 4.3: 1, 2, 3, 9, 10, 12, 13, 14, 15.
• Due Nov 28
  1. Chapter 6.1: 1, 3, 5, 6, 8, 9, 10, 13, 20, 25, 29, 33.
• Due December 6
  1. Chapter 6.3: 1, 2, 3, 6, 10, 12, 16, 28.

Quizzes

The weekly quizzes will be posted here.

• Quiz 1
• Quiz 2
• Quiz 3
• Quiz 4
• Quiz 5
• Quiz 6
• Quiz 7
• Quiz 8
• Quiz 9

Marking Scheme

Your course grade is computed as follows:

• Quizzes 25%
• Midterm 30%
• Final exam 45%

Study Hints

Before each class, you should both review the material from recent sections and read the section to be discussed that day. This will allow you to both understand the presentation of new material and identify questions that you need to resolve during class.

Academic Integrity

All students, faculty and staff are expected to follow the University's guidelines and policies on academic integrity. For students, this means following the standards of academic honesty when writing assignments, collaborating with fellow students, and writing tests and exams. Ensure that the work you submit for grading represents your own honest efforts. Plagiarism -- representing someone else's work as your own or submitting work that you have previously submitted for marks in another class or program -- is a serious offence that can result in sanctions. Speak to me or your TA for advice on anything that you find unclear. To learn more about how to cite and use source material appropriately and for other writing support, see the U of T writing support website here. Consult the Code of Behaviour on Academic Matters for a complete outline of the University's policy and expectations. For more information, please look here and here.

Policy on Missed Work or Class Participation

Verification of Illness forms (also known as a doctor's note) are temporarily not required. Students who are absent from class for any reason (e.g., COVID, cold, flu and other illness or injury, family situation) and who require consideration for missed academic work should report their absence through the online absence declaration. The declaration is available on ACORN under the Profile and Settings menu.

Accessibility Needs

The University of Toronto is committed to accessibility. If you require accommodations for a disability, or have any accessibility concerns about the course, the classroom or course materials, please contact Accessibility Services as soon as possible: email accessibility.services@utoronto.ca or visit here.

Mental Health Care

The Health and Wellness Centre offers mental health services to students. To get more information, visit their website here.