## MAT 332, Introduction to Graph Theory, Fall 2017

#### Instructor

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

#### Meetings

Tuesdays 2-4 pm in SS 2106.
Thursdays 3-4 pm in SS 2106.

#### Office hours

Tuesdays 12-2 pm or by appointment.

#### Teaching Assistant

Leonid Monin
Email: lmonin@math.toronto.edu
Leonid holds office hours on Mondays from 1-2 in the math lounge. You can also ask for an appointment if you the time does not work.

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

#### Prerequisite

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 24, 2-4 pm in SS 2106.

See this Midterm Guide to see what material from the textbook is covered in the midterm.

The final exam will take place on Monday December 18, 9-12 am in PB B150.

#### 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 (12 quizzes in total). Only the grades of the best 10 quizzes will count towards the final grade. Students are encouraged to work together on the homework problems.

#### Solutions

The solution to the quizes will be posted here.

#### Homework Problems

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

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

#### Policy on missed quizzes or exams:

There are no make up exams or quizzes. If you miss more than two quizzes or the midterm for a legitimate reason which you can document, your grading scheme will be adjusted by increasing the final exam component of your mark. The documentation must be submitted no later than 7 days after the date of the exam/quiz. You can find the University of Toronto Medical Certificate form here.