## 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
2. Chapter 1.2: 1, 3, 10, 12, 16, 18, 20, 22, 25, 28, 40
• Due September 27
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.

#### Marking Scheme

• 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.