MA 216: Introduction to Graph Theory

Instructor: Arvind Ayyer
Office: X-15 (new wing)
Phone number: (2293) 3215
Email: (First name) at iisc dot ac dot in
Class Timings: Tuesdays and Thursdays, 5:00–6:30pm.
Classroom: LH 1, Mathematics Department (first floor)
Office hours: By appointment
Textbooks: Graph theory
by Adrian Bondy and U.S.R. Murty
ISBN-13 - 978-1846289699

Graph theory
by Reinhard Diestel
ISBN-13 - 978-3540261827

Introduction to graph theory
by Douglas B. West
ISBN-10 - 0-13-227828-6
  • Subhajit Ghost (gsubhajit at iisc dot ac dot in)

Course Prerequisites

Basic linear algebra and some exposure to proofs and abstract mathematics.

Course Description

Graphs, subgraphs, Eulerian tours, trees, matrix tree theorem and Cayley's formula,
connectedness and Menger's theorem, planarity and Kuratowski's theorem, chromatic number
and chromatic polynomial, Tutte polynomial, the five-colour theorem, matchings, Hall's theorem,
Tutte's theorem, perfect matchings and Kasteleyn's theorem, the probabilistic method, basics of algebraic graph theory


All exams will be closed book, closed notes, and
no calculators or electronic devices are allowed.
No communication among the students will be tolerated.
There will be no make up exams.


Here are the weights for the homework and exams.
All marks will be posted online on Moodle.

Tentative Class Plan

Week 1 (Aug 6, 8): Sections 1.1-1.2 of B-M

Week 2 (Aug 13): Sections 1.2-1.4 of B-M
Homework 1 is here and is due on Aug. 22.

Week 3 (Aug 20, 22):

Week 4 (Aug 27, 29):

Week 5 (Sep 3, 5):

Week 6 (Sep 12):

Week 7 (Sep 17, 19):

Week 8 : Midsemester exam on Sep 24

Week 9 (Oct 1, 3):

Week 10 (Oct 10):

Week 11 (Oct 15, 17):

Week 12 (Oct 22, 24):

Week 13 (Oct 29, 31):

Week 14 (Nov 5, 7):

Week 15 (Nov 14):

Week 16 (Nov 19, 21):

Back to the homepage