Introduction
A graph is one of the most powerful and reusable ideas in all of computer science and mathematics. Whenever we have a set of objects and some notion of pairwise connection between them — cities joined by roads, computers joined by cables, people who are friends, web pages that link to each other, tasks that depend on one another — we are really looking at a graph. Graph Theory is the branch of Discrete Mathematics that studies these structures precisely.
For Bangladeshi government job exams (BCS, Bank IT-officer, and IT-officer posts), Graph Theory is a guaranteed scoring area. Questions are compact and formula-driven: counting edges, degrees, checking Euler/Hamiltonian paths, identifying trees, colouring, and using the Handshaking Lemma. Because the theory is small but the point-per-question is high, mastering this topic is one of the best returns on study time you can get.
Learning objectives
After studying this lesson you will be able to:
- Define a graph and all its basic components — vertex, edge, degree, adjacency, incidence.
- Distinguish directed vs undirected, simple vs multigraph, weighted vs unweighted graphs.
- State and apply the Handshaking Lemma and count edges/degrees confidently.
- Recognise special graphs: complete (Kₙ), cycle (Cₙ), path (Pₙ), bipartite, regular, and trees.
- Compute the number of edges in complete and complete-bipartite graphs from formulas.
- Understand walks, trails, paths, cycles, connectivity, and components.
- Decide when a graph has an Euler circuit/path and understand Hamiltonian paths.
- Represent a graph with an adjacency matrix and adjacency list.
- Apply graph-colouring basics and the four-colour idea.
- Avoid the classic exam traps and solve MCQ-style problems quickly.