Graphs: vocabulary, adjacency matrix vs adjacency list

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Children of node i in a 1-based heap? from Lesson 0.2.2
• Cost to search an unsorted array? from Lesson 0.2.1
• How many times can you halve n before reaching 1? from Lesson 0.1.2

1 · The Hook

🎣

Road maps, task schedules, social networks and the web are all graphs: dots joined by lines. Phase 6 runs BFS, DFS, MST and shortest-path algorithms on them, and their costs are always written in terms of V (vertices) and E (edges). This lesson sets the vocabulary and the two storage formats.

2 · Predict First

🤔

An undirected graph has 6 vertices with degrees 2, 3, 4, 4, 3, 2. How many edges does it have?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Each edge adds 1 to the degree of both its ends, so the degrees add up to twice the edges: (2 + 3 + 4 + 4 + 3 + 2) / 2 = 18 / 2 = 9 edges.

Vocabulary

• Graph G = (V, E): a set of vertices and a set of edges. |V| = n (or V), |E| = m (or E).
• Undirected edge {u, v} vs directed edge (u → v). Weighted: each edge has a number (length, cost).
• Degree of a vertex: number of edges at it. Directed: in-degree and out-degree.
• Handshake lemma: Σ degrees = 2|E| (undirected). Directed: Σ in-degrees = Σ out-degrees = |E|.
• Path: a sequence of vertices joined by edges; cycle: a path that returns to its start.
• Connected (undirected): a path between every pair. Strongly connected (directed): a directed path both ways between every pair.
• Tree: connected and acyclic; a tree on n vertices has exactly n − 1 edges.
• DAG: directed acyclic graph.
• A simple undirected graph has at most n(n − 1)/2 edges; a directed one at most n(n − 1). Few edges (E near V) = sparse; many (E near V²) = dense.

Storage

The running example: six towns

Undirected, weighted; vertices A–F; edges with lengths: A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 2, D–F 6, E–F 3. Degrees: A 2, B 3, C 4, D 4, E 3, F 2 (sum 18 = 2 × 9 edges).

4 · Visual

The six-town graph used throughout Phase 6 (edge labels are road lengths).

5 · Worked Examples

Example 1 Easy

How many entries does the adjacency matrix of a 100-vertex graph have?

Solution

100 × 100 = 10,000.

Example 2 Medium

A simple undirected graph on 12 vertices: maximum number of edges?

Solution

12 × 11 / 2 = 66.

Example 3 GATE

A tree has 25 vertices. How many edges? If one more edge is added between two of its vertices, how many cycles are created?

Solution

24 edges; the new edge closes exactly 1 cycle.

6 · GATE Traps

⚠️

• Handshake: degrees sum to 2E, not E.
• Adjacency-matrix algorithms usually cost Θ(V²) even for sparse graphs.
• A tree always has n − 1 edges.
• Directed simple graph: n(n − 1) edges max (both directions count).

7 · Memory Hook

🧠

"Matrix: V², fast lookup. List: V + E, fast scan."

8 · Connect the Dots

Phase 0 is complete: steps, math, and the price lists of arrays, lists, trees, heaps and graphs. Phase 1 makes "about n" and "about log n" precise: asymptotic notation and recurrences.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markHandshake

An undirected graph has 10 edges. What is the sum of all vertex degrees?

Numerical answer: ________

Q2NAT1 markTree edges

A tree on 40 vertices has how many edges?

Numerical answer: ________

Q3NAT2 marksMax edges

Maximum number of edges in a simple directed graph with 9 vertices?

Numerical answer: ________

Q4MCQ1 markRepresentation

For a sparse graph with V = 10⁶ and E = 3 × 10⁶, which representation uses less memory?

• (A) Adjacency list
• (B) Depends on the weights
• (C) Adjacency matrix
• (D) Both the same

Q5NAT2 marksDegrees

In the six-town graph, what is the degree of vertex D?

Numerical answer: ________

10 · Rule Card

• Σ degrees = 2E (undirected); Σ in = Σ out = E (directed).
• Tree: connected, acyclic, n − 1 edges. Max edges: n(n−1)/2 undirected, n(n−1) directed.
• Matrix: Θ(V²) space, O(1) edge test. List: Θ(V + E) space, O(deg) neighbours, O(V + E) scan.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

graph G = (V, E)directed and undirected edgesweighted graphdegree, in-degree, out-degreehandshake lemmapath and cycleconnected and strongly connectedtree has n − 1 edgesDAGsparse vs denseadjacency matrixadjacency listsix-town running example

12 · Answer Vault