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

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

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.

- NPTEL Graph Theory by Prof. S. A. Choudum
- NPTEL Graph Theory by Prof. Sunil Chandran
- Mathematics for Computer Science by Eric Lehman, F Thomson Leighton and Albert R Meyer.

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)

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 |

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) |