17622 Advanced graph theory, Spring 2003

students

Topics covered

Basic concepts and definitions
Graphs, subgraphs, bipartite graphs, graph isomorphism and automorphism, decomposition, union, disjoint union, join, vertex and edge deletion, paths, cycles, trails, connection in graphs, components, cut-vertex, cut-edge, Eulerian circuits, degree-sum formula, graphic sequences, the Petersen graph, hypercubes.

Trees
Forests and trees, spanning trees, distance in graphs, diameter, radius and eccentricity, center, Prüfer code, Cayley's formula, matrix tree theorem.

Matchings and factors
Matchings, maximal and maximum matchings, alternating and augmenting paths, Hall's matching condition, marriage theorem, vertex and edge covers, independent sets, algorithm for computing maximum bipartite matching, factors, Tutte's 1-factor theorem, Berge-Tutte formula, Petersen's results on 1-factors and 2-factors.

Cuts and connectivity
Vertex cuts and edge cuts, connectivity and edge-connectivity, bonds, blocks, block-cutpoint graphs, computing blocks using DFS, 2-connected graphs, Menger's theorem, Elias-Feinstein-Shannon-Ford-Fulkerson theorem.

Planarity
Planar embeddings, planar and plane graphs, dual graphs, outerplanar and outerplane graphs, Euler's formula, triangulation, Platonic solids, Kuratowski's theorem, graph coloring, Heawood's five-color theorem.

Books

[West] Douglas B West, Introduction to Graph Theory, second edition, Prentice Hall, India.
[Harary] Frank Harary, Graph Theory, Narosa Publishing House.

I will mostly follow [West]. [Harary] is a celebrated classical reference to the subject.

Tentative test schedule

TestPlace and TimeTotal pointsDuration SyllabusQuestionsAnswers
Class test I (Details below) Submit on or before February 17, 2003 10 Take-home Chapter 1 of [West] pdf, ps.gz pdf, ps.gz
Mid-semester exam CS108, Feb 27, 2003, FN (9:00-11:00) 302 hrs Till introduction to trees pdf, ps.gz pdf, ps.gz
Class test II (Details below) Submit on or before April 18, 2003 10Take-home Trees, Matching and factors, Cuts and connectivity, Planarity pdf, ps.gz pdf, ps.gz
End-semester exam CS108, April 28, 2003, FN (9:00-12:00) 503 hrs Whatever is taught, with emphasis on Chapter 2 onwards pdf, ps.gz pdf, ps.gz


Class Test I

Solve 5 problems from Exercise Set 1 and submit on or before February 17, 2003. If you submit electronically, mail me a ps or a pdf file. If you prefer to submit a handwritten document and can not contact me personally, drop your solutions in my mailbox (CSE building, ground floor). Now here is the list of exercises that you are supposed to solve and submit. (You are heartily encouraged to dirty your hands by solving the other 15 problems. Don't submit solutions of this complementary set. This is for your personal practice.)

Students   Exercises
Kaustav, Harish, Ravi, Anurag, Sundar, Mrinmoy     11,13,15,17,19.
Amitava, Prabhas, Subhradyuti, Suraj, Sandeep (and other registrants, if any)     12,14,16,18,20.


Class Test II

Solve 5 problems from Exercise Set 2 and submit on or before April 18, 2003. If you submit electronically, mail me a ps or a pdf file. If you prefer to submit a handwritten document and can not contact me personally, drop your solutions in my mailbox (CSE building, ground floor). Now here is the list of exercises that you are supposed to solve and submit. (We have solved some of the remaining exercises in a tutorial session on last Friday (April 11). We plan to have another tutorial session on April 18. Also note that you need something called Euler's formula for solving the last problem. I will prove this divine result on next Wednesday (April 16).)

Students   Exercises
Kaustav, Harish, Ravi, Anurag, Sundar, Mrinmoy     5,11,13,19,24.
Amitava, Prabhas, Subhradyuti, Suraj, Sandeep (and other registrants, if any)     6,12,18,20,25.


Practice exercises



Other resources

Slides from Prof Pallab Dasgupta.

Home