Unit - 1 Introduction to Graph Theory:

1.1 Definitions and Examples

1.2 Subgraphs, Complements and Graph Isomorphism

1.3 Vertex Degree, Euler Trails and Circuits.

Unit – 2 Introduction to Graph Theory contd.:

2.1 Planar Graphs

2.2 Hamilton Paths and Cycles

2.3 Graph Colouring and Chromatic Polynomials.

Unit - 3 Trees:

3.1 Definitions, Properties and Examples, Rooted Trees, Trees and Sorting, Weighted Trees and Prefix Codes

Unit - 4 Optimization and Matching:

4.1 Optimization and Matching: Dijkstra’s Shortest Path Algorithm

4.2 Minimal Spanning Trees, The algorithms of Kruskal and Prim, Transport Networks

4.3 Max-flow, Min-cut Theorem, Matching Theory.

Unit - 5 Fundamental Principles of Counting:

5.1 Fundamental Principles of Counting: The Rules of Sum and Product, Permutations, Combinations

5.2 The Binomial Theorem, Combinations with Repetition, The Catalon Numbers

Unit - 6 The Principle of Inclusion and Exclusion:

6.1 The Principle of Inclusion and Exclusion, Generalizations of the Principle

6.2 Derangements – Nothing is in its Right Place, Rook Polynomials.

Unit - 7 Generating Functions:

7.1 Introductory Examples, Definition and Examples

7.2 Calculational Techniques, Partitions of Integers, The Exponential Generating Function, The Summation Operator.

Unit - 8 Recurrence Relations:

8.1 Recurrence Relations: First Order Linear Recurrence Relation, The Second Order Linear Homogeneous Recurrence Relation with Constant Coefficients, The Non-homogeneous Recurrence Relation

8.2 The Method of Generating Functions.