MAT 332, Introduction to Graph Theory, Fall 2022
InstructorProf. Kasra Rafi
Office: BA 6236 (Bahen Centre)
MeetingsTuesdays 1-3 pm in SS 2108.
Thursdays 2-3 pm in SS 2108.
Office HoursTuesdays 12-1 pm, Thursdays 1-2 pm or by appointment.
Teaching AssistantsVivian He
TextbookIntroduction to Graph Theory, 2nd Edition, by Douglas B. West.
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.
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.
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.
- Due September 13
- Due September 20
Due September 27
- Read Chapter 1.2
- Chapter 1.2: 1, 3, 10, 12, 16, 18, 20, 22, 25, 28, 40
- Read Chapter 1.3
- Chapter 1.3: 1, 2, 4, 7, 13, 18, 26, 31, 36, 41, 44, 47, 64
- Chapter 1.4: 3, 4, 7, 8, 12, 14, 20, 22, 29, 36
- Chapter 2.1: 2, 4, 7, 12, 14, 16, 24, 36, 37, 49
- Chapter 2.2: 7, 8, 9
- Chapter 3.1: 1, 3, 8, 10, 11, 18, 21, 26, 30, 42
- Chapter 4.1: 1, 5, 8, 10, 12, 14, 18
- Chapter 4.1: 2, 15, 24, 25, 28, 30, 32
- Chapter 4.2: 1, 2, 4, 6, 10
- Chapter 4.3: 1, 2, 3, 9, 10, 12, 13, 14, 15.
- Chapter 6.1: 1, 3, 5, 6, 8, 9, 10, 13, 20, 25, 29, 33.
- Chapter 6.3: 1, 2, 3, 6, 10, 12, 16, 28.
The weekly quizzes will be posted here.
- Quizzes 25%
- Midterm 30%
- Final exam 45%
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.
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 ParticipationVerification 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.
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 email@example.com 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.