MA 216: Introduction to Graph Theory
Instructor:

Arvind Ayyer

Office:

X15 (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
ISBN13  9781846289699
Graph theory
by Reinhard Diestel
ISBN13  9783540261827
Introduction to graph theory
by Douglas B. West
ISBN10  0132278286

TA:

 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 fivecolour theorem, matchings, Hall's theorem,
Tutte's theorem, perfect matchings and Kasteleyn's theorem, the probabilistic method, basics of algebraic graph theory
Exams
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.
Grading
Here are the weights for the homework and exams.
All marks will be posted online
on Moodle.
 5% – Attendance
 15% – Homeworks
 30% – Midterm
 50% – Final (Nov 30: 2pm  5pm)
Tentative Class Plan
Week 1 (Aug 6, 8): Sections 1.11.2 of BM
Week 2 (Aug 13): Sections 1.21.4 of BM
Homework 1 is
here and is
due on Aug. 22.
Week 3 (Aug 20, 22): Sections 2.12.5, 3.13.3 of BM
Week 4 (Aug 27, 29): Sections 18.1, 18.3, 4.14.2 of BM
Homework 2 is
here and is
due on Sep. 5.
Week 5 (Sep 3, 5): Cayley's theorem, Section 5.1 of BM
Week 6 (Sep 12): Sections 5.2, 5.3 of BM
Homework 3 is
here and is
due on Sep. 19.
Week 7 (Sep 17, 19): Sections 7.17.2 of BM
Week 8 : Midsemester exam on Sep 24: 56:30pm
Week 9 (Oct 1, 3): Sections 7.3, 9.1 of BM
Week 10 (Oct 10): Section 9.1 of BM
Week 11 (Oct 15, 17): Sections 10.110.3 of BM
Week 12 (Oct 22, 24): Sections 10.410.5 of BM
Homework 4 is
here and is
due on Oct. 31.
Week 13 (Oct 29, 31): Sections 16.116.3 of BM
Week 14 (Nov 7): Kasteleyn theory
Week 16 (Nov 19, 21): Section 14.1 of BM
Final on Nov 30: 2pm  5pm