3.1Graph representations and basic facts
The idea
A graph has vertices and edges. It is stored as an adjacency matrix (V² cells) or adjacency lists (V + E entries).
Think of it like this: A map of cities and roads.
Why it exists
Counting edges, degrees and storage are warm-up questions in every graph set.
How it works
- Sum of degrees = 2E (handshake lemma).
- Simple undirected graph: at most V(V − 1)/2 edges; connected needs ≥ V − 1.
- Matrix: O(1) edge test, V² space. List: V + E space.
- A tree is a connected acyclic graph with exactly V − 1 edges.
Worked example: V = 10 vertices
A simple undirected graph has at most 45 edges, a directed one at most 90. A connected one needs at least 9.
Now play with it
- →Move V and E in the calculator.
- →Check when the list becomes bigger than the matrix.
Dense graph (E ≈ V²): matrix is fine. Sparse graph (E ≈ V): use lists.
Check yourself
The maximum number of edges in a simple undirected graph on 8 vertices is
Exam notes (the dense version)
An adjacency matrix uses Θ(V²) space with O(1) edge test; an adjacency list uses Θ(V + E) with O(degree) edge test. Sum of degrees = 2E. A simple undirected graph has at most V(V − 1)/2 edges; a connected one has at least V − 1; a tree has exactly V − 1 and no cycle. A simple directed graph has at most V(V − 1) edges.
Previous year questions: Graph Algorithms (35)
PYQs are grouped by topic, so this is the full set for Graph Algorithms; try the ones that match this subtopic. Open all 35 on the topic page.