**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.

# Past Offerings

- Offered in Jan-May, 2023 by Srimanta Bhattacharya
- Offered in Jan-May, 2022 by Krithika Ramaswamy
- Offered in Jan-May, 2021 by Jasine

# Course Metadata

Item | Details |
---|---|

Course Title | Graph Theory and Combinatorics |

Course Code | CS5010 |

Course Credits | 3-0-0-3 |

Course Category | PMT |

Proposing Faculty | Deepak Rajendraprasad |

Approved on | Senate 11 of IIT Palakkad |

Course status | NEW |