Graph Theory & Representations

The last lesson ended by tearing up the tree’s rule book: no single root, no ban on cycles, no one-parent-per-node. What you are left with is the most general relationship structure there is — a graph. A graph is simply a set of vertices (nodes) joined by edges (connections). Friendships, road networks, task dependencies, web links — all graphs; so are the dependency DAG behind every Spark or Airflow pipeline and the data feeding a graph neural network. Before any traversal algorithm makes sense, you need the vocabulary and the two standard ways to store a graph in memory. That is this lesson.

Vertices, edges, and direction

Formally a graph is a pair G = (V, E), where V is the set of vertices and E is the set of edges. Two flavours:

• Undirected — an edge {u, v} is symmetric: if u connects to v, then v connects to u. Facebook friendships.
• Directed (a digraph) — an edge (u, v) is an arrow from u to v and says nothing about the reverse direction. Twitter follows.

Degree counts a vertex’s edges. In an undirected graph the degree of a vertex is the number of edges touching it. In a directed graph you split this into in-degree (arrows arriving) and out-degree (arrows leaving).

Paths, cycles, connectivity, DAGs, trees

• A path is a sequence of vertices where consecutive ones are joined by an edge.
• A cycle is a path that returns to its start (and repeats no edge).
• A graph is connected if there is a path between every pair of vertices.
• A DAG (directed acyclic graph) is a directed graph with no directed cycle — the structure behind task scheduling and the only graph that can be topologically sorted (next lesson).
• A tree is a connected acyclic graph — exactly the restricted shape from last lesson. A key fact: a tree on V vertices has exactly V − 1 edges — add one more edge and you create a cycle; remove one and it disconnects.

Two ways to store a graph

How you store a graph decides which operations are cheap. The two standard choices:

• Adjacency matrix — a V × V grid where cell (i, j) = 1 if an edge joins i and j, else 0. O(V²) space, but checking “is there an edge i-j?” is O(1). For an undirected graph the matrix is symmetric.
• Adjacency list — for each vertex, store a list of its neighbours. O(V + E) space, which is far smaller when the graph is sparse (few edges). Listing a vertex’s neighbours is direct; an edge-existence check costs up to O(degree).

Explore the trade-off live — click an edge and watch it light up in both the list and the matrix, and toggle directed/undirected to see the matrix symmetry change:

How GATE asks this

Expect a NAT or MCQ. Common patterns: “given the degree sequence, how many edges?” (use the handshake fact), “how many edges in a complete graph on n vertices?” (n(n−1)/2), “how much space does an adjacency matrix need?” (O(V²)), and terminology checks on DAGs and trees. These are fast marks if the definitions are reflexes.

Worked example

Take an undirected graph on 4 vertices with edge set { (1,2), (1,3), (1,4), (2,4) } — that is 4 edges (the graph drawn above).

Step 1 — degrees. Count edges at each vertex:

deg(1) = 3   (joins 2, 3, 4)
deg(2) = 2   (joins 1, 4)
deg(3) = 1   (joins 1)
deg(4) = 2   (joins 1, 2)

Step 2 — verify the handshake fact. Sum of degrees = 3 + 2 + 1 + 2 = 8, and 2 × |E| = 2 × 4 = 8. They match.

Step 3 — representations. The adjacency matrix is the symmetric grid above; the adjacency list is 1 → 2,3,4, 2 → 1,4, 3 → 1, 4 → 1,2.

Step 4 — a complete graph. If these 4 vertices were all mutually connected, the edge count would be C(4, 2) = 4·3/2 = 6. Our graph has only 4 of those 6 possible edges, so it is not complete.

A question to carry forward

You can now store a graph and count its edges — but a graph earns its keep only once you can walk it: find a path from here to there, visit every reachable city, or order a pile of tasks so that prerequisites always come first. And walking a graph is genuinely harder than walking a tree, for one reason the last lesson forbade and this one allows: cycles. With no root to start from and loops that can send you round and round forever, exploration needs real discipline. Here is the thread into the final lesson of this chapter: how do you systematically visit a graph’s vertices — breadth-first and depth-first — without getting lost or circling endlessly, and how does that same machinery order tasks and find shortest paths?

In one breath

• A graph G = (V, E): vertices joined by edges. Undirected (symmetric) vs directed (arrows); degree = edges touching a vertex (split into in/out for digraphs).
• Handshake fact: sum of degrees = 2 × |E| (each edge counted at both ends).
• Complete graph on n vertices: n(n−1)/2 edges. Tree = connected + acyclic = exactly V − 1 edges. DAG = directed + no cycle.
• Adjacency matrix: O(V²) space, O(1) edge check (symmetric if undirected). Adjacency list: O(V + E) space, best for sparse graphs.
• Traps: degree sum is 2|E| not |E|; a matrix is O(V²) even when sparse; a tree has V − 1 edges, not V.

Practice