Review of Graphs: Graphs and Sub graphs, isomorphism, matrices associated with graphs, Degrees, walks, connected graphs, shortest path algorithm.

Trees: Trees, cut-edges and cut-vertices, spanning trees, minimum spanning trees, DFS, BFS Algorithms.

Connectivity: Graph connectivity, k-connected graphs and blocks.

Euler and Hamilton Graphs: Euler graphs, Euler’s theorem. Fleury’s algorithm for Eulerian Trails. Necessary / sufficient conditions for the existence of Hamilton cycles, Chinesepostman- Problem, approximate solutions of traveling salesman problem

Matching Matchings, maximal matchings. Coverings and minimal coverings. Berge’s Theorem, Hall’s theorem, Tutte’s perfect matching theorem, Job assignment problem. Coverings, Independent Sets and Cliques; Basic Relations.

Colorings: Vertex colorings, greedy algorithm and its consequences, Brooks’ theorem. Edgecolorings,

Vizing theorem on edge-colorings.

Planar graphs: Euler formula. Dual graphs. Kuratowaski’s Characterization, Planarity Testing algorithm.

Course Outcomes
CO-1: Understand the basic concepts of graphs and trees.
CO-2: Understand and apply the concepts of graph connectivity and shortest path Problems.
CO-3: Understand and apply the concepts of matching problems in job assignments.
CO-4: Understand the concepts of vertex and edge colorings.
CO-5: Understand the concepts of planar graphs and dual graphs.

Textbook

1. J.A. Bondy and U.S.R. Murty, Graph Theory and Applications, Springer, 2008.

References Books

1. 1. D.B. West, Introduction to Graph Theory, P.H.I. 2010.
   2. Frank Harary, Graph Theory, New York Academy of Sciences, 1979.
   3. Russel Merris, Graph Theory, John Wiley, 2011.