Simple Graphs – Graph Isomorphism – The Incidence and Adjacency matrices – Sub graphs – Vertex Degrees – paths and Connection – Cycles, Trees – Cut edges and Bonds – cut vertices – Cayley’s formula.

Blocks, Euler tours and Hamilton Cycles.

Matchings, coverings in Bipartite Graphs – Perfect Matchings. Edge colourings: Edge chromatic number.

Independent sets – Ramsey’s theorem. Vertex Colourings: Chromatic Number – Brook’s Theorem – Hajos Conjecture – Chromatic Polynomials – Girth and Chromatic number.

Plane and planar Graphs – Dual Graphs – Euler’s formula. The Five Colour Theorem and the Four Colour Conjecture – Non-Hamiltonian planar Graphs. Directed Graphs – Directed paths - Directed cycles.