• Class timing: Tuesday and Thursday, 9:30 am - 11:00 am
  • Venue: CSA 252

  • Ashwin Guha (Email: guha_ashwin@csa.iisc.ernet.in)
  • Office Hours: Friday 3 pm - 5 pm

The course is shared between two instructors and I will be teaching the second half.

  • Quiz + Assignment in the first half: 10%
  • Mid-term Exam in the first half: 40%
  • Two class-tests in the second half: 5% each
  • "Chalk & Talk a Graph Theorem" Session in the second half: 10%
  • Final Exam in the second half: 30%

The course aims to cover the following areas in Discrete Structures: Basic Mathematical Notions, Counting and Combinatorics, Number Theory, Graph Theory, Group and Field Theory. The first half of the course covers: Basic Mathematical Notions, Counting and Combinatorics, Number Theory (Link to the first half of the Course). The second half will deal with: Graph Theory, Group and Field Theory.

Reference Books:

  • K.H.Rosen, Discrete Mathematics and applications, fifth edition 2003, TataMcGraw Hill publishing Company.
  • J. A. Bondy and U. S. R. Murty. Graph Theory, volume 244 of Graduate Texts in Mathematics. Springer, 1st edition, 2008. Soft copy available here (Warning! Don't try to print the document. It's a very old document and so printing it will eat up a lot of ink and may cause printer jam).
  • R. Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, 2nd edition, 2000.
  • Herstein I N : Topics in Algebra, 2 ed., Wiley India 1975.
Some useful Course Notes/Lectures:

A set of problems will be posted below after every class based on the topics covered in the class. You are not required to submit the answers. Please approach the problems in three steps in the order they are listed: (1) Think, think, think (think more; the more the better), (2) Discuss and try together with friends (3) Resort to google. If one chooses to get them done in the reverse order, then (s)he is cheating herself/himself not me. So choice is yours. The problems are brain teasers and will train you in critical thinking. Also they give you an idea about what you may find in the class-tests and final exam. Try solving problems from other sources as well.

  • Office Hours: Tuesday Thursday 11:30 am - 12:30 am or by appointment
  • Google group for the course
  • Link to the first half of the Course

  • When: 9th December; 8 AM - 1 PM
  • Where: CSA 252 (Multimedia Room)
  • Credit: 30 (20 for Graph theory + 10 for Algebra & Coding Theory)

Lecture Details

Will be updated as and when the course progresses.

Lecture # and Date
Lecture contents
Reading material
Problem Set
Lecture 1 (30-09-2014) Definition of Graph, Basic terminologies, Graph Isomorphism, Subgraphs (Spanning and Induced), Adjacency and Incidence Matrix, Degree and neighbors of a vertex, Special Graphs. Problem Set 1 (Q1.1 corrected; thanks to Sumant, Pankaj and Indranil for pointing out a bug in the question)
No Lecture (02-10-2014)- Gandhi Jayanti
Lecture 2 (07-10-2014) Operations on graph (Complement, Union and Sum), Graph theoretic model of LAN problem, Degree Sequence, Graphic Sequence and realization of a graphic sequence, Havel-Hakimi Criterion, Realization of a graphic sequence using Havel-Hakimi Criterion. Problem Set 2
Lecture 3 (09-10-2014) Erdos-Gallai Criterion, Walk, Trail, Path, Cycle, Sufficient conditions for a simple graph to contain a cycle (of some length AND of length >= 1+ minimum degree of a graph), Girth and Circumference Problem Set 3
Lecture 4 (10-10-2014; Time: 9:30 am to 11 am)- Makeup Class of 14-10-2014 Connected Graph, Components, necessary condition for a graph to be connected, relation among m(G), n(G) and c(G), necessary and sufficient condition for a graph to contain a cycle, Distance and Diameter, Cut-vertex, cut-edge and their characterizations. Problem Set 4
Lecture 5 (12-10-2014; Time: 11:00 am to 12:30 pm)- Makeup Class of 16-10-2014 Vertex-cut, vertex-connectivity, Edge-cut, Edge Connectivity, Whitney's theorem relating vertex connectivity, edge connectivity and minimum degree of a graph, Whitney's theorem on characterization of 2-connected graphs (special case of Menger's Theorem), Tree, Various Characterizations of Tree. Problem Set 5
No Lecture (14-10-2014)- Instructor out of town
No Lecture (16-10-2014)- Instructor out of town
Tutorial by Ashwin (17-10-2014; Time: 2 pm - 3:30 pm) Problem Set 1 - 3
First Quiz (Time: 8:55 am to 9:55 am) + Lecture 6 (21-10-2014) Chvatal's theorem (Sufficiency of a graph to contain all possible trees on k vertices), Cayley's formula for number of trees on n vertices, Prüfer's proof for Cayley's formula (partly completed) Problem Set 6
No Lecture (23-10-2014)- Deepavali
Tutorial by Ashwin (24-10-2014; Time: 2 pm - 3:30 pm) Problem Set 4 PLUS Quiz 1 questions
Lecture 7 (28-10-2014) Prüfer's proof for Cayley's formula (completed), Eulerian Trail, Closed Eulerian Trail, Euler Graphs, Charaterization of Euler Graphs (Euler's theorem), Fluery's Algorithm to find a closed Eulerian Trail, Demonstration. Problem Set 7
Lecture 8 (30-10-2014) Proof of correctness of Fluery's Algorithm, Hamilton Path & Cycle, Hamilton Graph, Two Necessary conditions, Dirac's Sufficiency condition, Ore's Sufficiency Condition, Ore's subsumes Dirac, Sufficiency Condition due to Chvatal & Erdos. Problem Set 8
No Lecture (04-11-2014)- Muharram
No Lecture (06-11-2014)- Guru Nanak's Birthday
Tutorial by Ashwin (08-11-2014; Time: 11 am - 12:30 pm) Problem Set 5-8 PLUS Quiz 1 answer scripts hand over
Lecture 9 (11-11-2014) k-vertex-coloring, Vertex-chromatic no., applications, lower bounds and upper bounds on vertex-chromatic no.-- relations between clique no. and vertex-chromatic no., Mycielski's theorem, relations between independence no. and vertex-chromatic no., relations between maximum degree and vertex-chromatic no. Problem Set 9
Second Quiz (8:20 am - 9:20 am) + Lecture 10 (13-11-2014) k-edge-coloring, Matching no. Edge-chromatic no., Gupa-Vizing's Theorem, Class 1/2 Graphs Problem Set 10
Lecture 11 (18-11-2014) Algebra, Basics- Axioms, Semi-groups, Monoid, Groups; Group: Subgroups, group properties. Group Generators, Cyclic Groups, properties of cyclic group.
Lecture 12 (19-11-2014) Cosets, Lagrange's Theorem and Its Implications, Group with Z_k/Z*_k and addition/multiplication modulo an integer, Group Homomorphism and Isomorphism, Introduction to Coding theory, Group Code.
Lecture 13 (25-11-2014) Group Code: Necessary / Sufficiency Conditions; Matrix Codes: Generator & Parity Check Matrices, Encoding / Decoding, Distance, Error Correction Capability; Hamming Code; Field; Special field Z_q; Polynomials over Z_q; Reed-Solomon Codes: Properties, Berlekamp & Welch Decoding Algorithm, Applications Reading materials for Reed-Solomon Codes: 1 & 2

"Chalk & Talk a Graph Theorem" Session

The list of graph theorems that will be covered in this session is available here. The sample tex file for the report can be downloaded from here (please use it to ensure uniformity).

Group # and members
Date and Time
Theorem and Theme
Reading material
Submitted File
Group 1- Anurita Mathur, Divya Ravi 20.11.14; 8:20 am - 8:50 am 1.1 (Menger's Theorem); Connectivity Menger's Theorem (On time)
Group 2- Arnab sen, Ramit 20.11.14; 8:55 am - 9:25 am 1.2 (Chvatal's Theorem); Hamilton Graph Chvatal's Theorem (On time)
Group 3- Priyank parihar, Sumant Hegde 20.11.14; 5:05 pm - 5:35 pm 1.3 (Ramsey's Theorem); Interplay of clique no and independence no. Ramsey's Theorem (Late)
Group 4- girijanandan Nucha , Datta Krupa 20.11.14; 5:40 pm - 6:10 pm 1.4 (Brook’s Theorem); Vertex Coloring Brook’s Theorem (On time)
Group 5- Ajith S, Pankaj 20.11.14; 6:15 pm - 6:45 pm 1.5 (Konig’s Theorem); Edge Coloring Konig’s Edge Coloring Theorem (On time)
Group 6- Indranil,Sayan Biswas 21.11.14; 8:15 am - 8:45 am 1.6 (Kuratowski's Theorem); Planarity Kuratowski's Theorem (On time)
Group 7- Priyanka Mondal, Lohit Krishnan 21.11.14; 8:50 am - 9:20 am 1.7 (Heawood's Theorem); Vertex coloring of Planar Graphs Heawood's Theorem (On time)
Group 8- Dheeraj Ram, Nithin V Nath 21.11.14; 9:25 am - 9:55 am 1.8 (From Kirchoff's Matrix Tree Theorem to Cayley's Theorem); Tree Counting Kirchoff to Cayley (On time)
Group 9- Abhijat Sharma, Mayank Tiwari 21.11.14; 10:00 am - 10:30 am 1.9 (Turan's Theorem); Extremal GT Turan's Theorem (On time)
Group 10- Tarun Bansal, Abhishek Jaiswal 21.11.14;2:00 pm - 2:30 pm 1.10 (Hall's Theorem); Matching in Bipartite Graph Hall's Theorem (Late)
Group 11- Surabhi Akotiya, Shaifali Gupta 21.11.14; 2:35 pm - 3:05 pm 1.11 (Konig's Theorem); Interplay of Matching No and vertex covering no in Bipartite Graph Konig's Theorem (On time)
Group 12- Arshed Nabeel, Toms Varghese 21.11.14; 3:10 pm - 3:40 pm 1.12 (Tutte's Theorem); Perfect Matching Tutte's theorem (On time)
Group 13- Pankaj Gautam, Lakhpat Meena 21.11.14; 4:00 pm - 4:30 pm 1.13 (Dirac's Theorem); Chordal Graph Dirac's Theorem (On time)
Group 14- Aakar Deora, Lawqueen Kanesh 21.11.14; 4:35 pm - 5:05 pm 1.14 (Krausz's Theorem); Line Graph Krausz's Theorem (Late)