Introduction to Graphs: 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.

Eulerian and Hamiltonian graphs: Euler graphs, Operations on graphs, Hamiltonian paths and circuits, Travelling salesman problem.

Directed graphs: types of digraphs, Digraphs and binary relation.

Trees: properties, pendant vertex, Distance and centres in a tree Rooted and binary trees, counting trees, spanning trees.

Connectivity Graphs: Vertex Connectivity, Edge Connectivity, Cut set and Cut Vertices, Fundamental circuits.

Planar Graphs: Planar graphs, Kuratowski’s theorem (proof not required), Different representations of planar graphs, Euler’s theorem, Geometric dual.

Graph Representations: Matrix representation of graphs-Adjacency matrix, Incidence Matrix, Circuit Matrix, Path Matrix.

Graph Colouring: Colouring Chromatic number, Chromatic polynomial, Matchings, Coverings, Four colour problem and Five colour problem. Greedy colouring algorithm.