# Course

## M661 - Combinatorics and Graph Theory

Course No:
M661
Credit:
4
Approval:
2014
PG-Core
Syllabus:

Pigeonhole principle, Counting principles, Binomial coefficients, Principles of inclusion and exclusion, recurrence relations, generating functions, Catalan numbers, Stirling numbers, Partition numbers, Schroder numbers. [25 lectures]

Graphs, subgraphs, graph isomorphisms, Hamilton cycles, Euler tours, directed graphs, matching, Tutte’s theorem, Menger’s theorem, planar graphs, Kuratowski’s theorem, graph colourings, network flows, max-flow min-cut theorem, Ramsey theory for graphs, Matrices associated with graphs: Incidence matrix, Adjacency matrix, Laplacian matrix. [25 lectures]

Reference Books:
1. R. A. Brualdi, Introductory Combinatorics, Pearson Prentice Hall, 2010.
2. J. H. van Lint, R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 2001.
3. R. P. Stanley, Enumerative Combinatorics Vol. 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, 2012.
4. R. Diestel, Graph Theory, Graduate Texts in Mathematics, 173, Springer, 2010.
5. B. Bollobas, Modern Graph Theory, Graduate Texts in Mathematics, 184, Springer-Verlag, 1998.
6. J. A. Bondy, U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics, 244, Springer, 2008.