**Code:**CS5010 |

**Category:**PMT |

**Credits:**3-0-0-3

# Course Objective

The objective of this course is to introduce the students to various techniques in graph theory and combinatorics.

# Course Contents

Matching, Hall's Theorem, Kőnig's Theorem, Connectivity, Coloring, Planar Graphs, Eulerian Graphs, Hamiltonian cycles, Dirac's Theorem, Ore’s Theorem. (12 lectures)

Introduction to Ramsey Theory and Extremal Graph Theory. (8 lectures)

Ordinary, Exponential and other special Generating Functions, Formal Power Series. (10 lectures)

Linear Algebraic Arguments like Dimensionality, Orthogonality and Rank arguments. Introduction to Spectral Graph Theory. (12 lectures)

# Learning Outcomes:

By the end of this course, students will be able to state, explain, prove, and apply fundamental results in graph theory and combinatorics. They will be able to analyse these proofs and apply these proof techniques to solve similar problems.

# Text Books:

- Reinhard Diestel, Graph Theory, Fifth Edition, Springer-Verlag Berlin Heidelberg, 2017, ISBN: 978-3-662-53621-6.
- F. R. K Chung, Spectral Graph Theory, ISBN: 978-0-8218-0315-8.
- László Babai and Péter Frankl, Linear Algebra Methods in Combinatorics With Applications to Geometry and Computer Science, Preliminary Version 2, 1992.

# References:

- Adrian Bondy and U. S. R. Murty, Graph Theory, Springer, 2008 Edition, ISBN: 978- 1849966900.
- Chris Godsil and Gordon Royle, Algebraic Graph Theory, Springer, 2001, ISBN: 978-0- 387-95220-8.
- Norman Biggs, Algebraic Graph Theory, Cambridge University Press, 1994. ISBN-13: 978- 0521458979.
- D.B West, Introduction to Graph Theory, Prentice Hall, 1996. ISBN: 9780132278287.

# Metadata

Proposing Faculty: Department: Computer Science and Engineering Programme: B.Tech Proposing date: Approved date: Proposal type: Offerings: