Graph Theory & Representations

A graph is the simplest structure for relationships: a set of vertices (nodes) joined by edges (connections). Friendships, road networks, task dependencies, web links — all graphs. So are the dependency graph (DAG) behind every Spark or Airflow pipeline and the data behind graph neural networks. 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. 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.

Quick check