Course Details:

Basics: Graphs, subgraphs, isomorphism, representation of graphs, degrees and graphical sequences, walks, trails, paths, cycles, Connectivity, bipartite graphs.

Trees and connectivity: Characterizations of trees, minimum-spanning-trees, number of trees, Cayley's formula, shortest path algorithms, cut-sets, Characterization of blocks.

Eulerian and Hamiltonian graphs: Characterizations, Necessary/sufficient conditions.

Coverings and independent sets: Basic relations, matchings in bipartite graphs, Tutte's Perfect matching theorem and consequences.

Colorings: Edge-colorings of bipartite graphs, Gupta Vizing's theorem, greedy algorithm for vertex-colorings, Brook's theorem, clique-number and vertex chromatic number.

Planar graphs: Euler's formula and its consequences, Kuratowski's Characterization.

Directed graphs: Basics, various connectivities and tournaments.

Text Book:

  1. J.A Bondy and U.S.R Murthy, Graph Theory with Applications, Macmillan, 1976.

Reference Book:

  1. D.B. West, Introduction to Graph Theory, P.H.I 1999.