What You will Learn ?

Module 1

Introduction- Basic definition – Application of graphs – finite, infinite and bipartite graphs – Incidence and Degree – Isolated vertex, pendant vertex and Null graph. Paths and circuits – Isomorphism, sub graphs, walks, paths and circuits, connected graphs, disconnected graphs and components.

Module 2

Euler graphs, Operations on graphs, Hamiltonian paths and circuits, Travelling salesman problem. Directed graphs – types of digraphs, Digraphs and binary relation, Directed paths, Fleury’s algorithm.

Module 3

​​​​​​​Trees – properties, pendant vertex, Distance and centers in a tree - Rooted and binary trees, counting trees, spanning trees, Prim’s algorithm and Kruskal’s algorithm, Dijkstra’s shortest path algorithm, Floyd-Warshall shortest path algorithm.

Module 4

Vertex Connectivity, Edge Connectivity, Cut set and Cut Vertices, Fundamental circuits, Planar graphs, Kuratowski’s theorem (proof not required), Different representations of planar graphs, Euler's theorem, Geometric dual.

Module 5

Matrix representation of graphs- Adjacency matrix, Incidence Matrix, Circuit Matrix, Path Matrix. Coloring- Chromatic number, Chromatic polynomial, Matchings, Coverings, Four color problem and Five color problem. Greedy coloring algorithm.