Graph Theory: Networks, Connections, and Relationships

The Delhi Metro Map Is Lying to You

If you have ever ridden the Delhi Metro, you have studied a graph without knowing it. Look at the route map on the coach wall. Rajiv Chowk is drawn as a neat circle connected by straight coloured lines to Kashmere Gate, Chandni Chowk, and half a dozen other stations. Here is the strange part: on the real map above ground, Kashmere Gate is not in a straight line from Rajiv Chowk, the distances on paper have nothing to do with the distances in kilometres, and the map is not drawn to any scale at all. A station that looks "close" on the map might be 6 km away, while a station drawn farther might be 2 km away.

The metro map is not trying to be geographically accurate. It is trying to answer one question only: which stations connect directly to which other stations? Everything else — distance, direction, the actual shape of the tunnels — is thrown away on purpose, because it isn't the information a passenger needs. That single idea, "keep only the connections, discard everything else," is the entire seed of graph theory. Once you strip a system down to "things" and "the connections between things," you have a graph, and the same handful of tools used to reason about metro maps will let you reason about WhatsApp groups, road networks, flight schedules, the internet's routers, and the recommendation system that decides what shows up in your Instagram feed.

What Exactly Is a Graph?

Formally, a graph is a pair G = (V, E) where:

• V is a set of vertices (also called nodes) — the "things". In the metro map, the vertices are stations.
• E is a set of edges — the connections between pairs of vertices. In the metro map, an edge exists between two stations if there is a direct track segment joining them, with no other station in between.

The number of vertices, |V|, is called the order of the graph, and the number of edges, |E|, is called its size. These are just counts — don't let the formal-sounding names intimidate you.

Let's build a small, concrete graph and work with it for the rest of this chapter, the way you'd sketch a mini metro corridor with six stations:

Vertices: A (Rajiv Chowk), B (Kashmere Gate), C (Chandni Chowk), D (New Delhi), E (Patel Chowk), F (Chawri Bazar)

Edges (direct track segments): A–B, A–D, B–C, B–E, C–F, D–E, E–F

Here, |V| = 6 and |E| = 7. Notice that a vertex doesn't need to be a place. A vertex can be a person (in a friendship network), a web page (in the World Wide Web), a task (in a project schedule), or a cricket team (in a tournament's results chart). What makes something graph theory is not the subject matter — it's the structure of "discrete things plus pairwise connections."

Directed vs. Undirected Graphs

In our metro graph, if you can travel from A to B, you can also travel from B to A on the same track (metros run both directions). An edge like this, with no arrow, is called undirected — the connection works both ways, and the edge A–B is the exact same object as B–A.

Not every real network works this way. Think about Instagram: if Riya follows Aman, it does not mean Aman follows Riya back. "Following" only points in one direction. A graph where edges have a direction — drawn as an arrow — is called a directed graph (often shortened to digraph). In a directed graph, the edge A → B is a completely different object from B → A; a graph can even contain both.

Some more directed examples worth noticing: a one-way street in a city (you can drive from junction P to junction Q but not back), a train timetable (train departs Chennai for Bengaluru, not automatically the reverse trip), or "Team India beat Pakistan" in a tournament results chart (the win only points one way). Compare that to undirected examples: WhatsApp contacts (if you're in my contacts through a shared number, it's mutual by nature of how the app works), a road that permits two-way traffic, or "these two students sit on the same school bus."

Unless stated otherwise, the rest of this chapter uses undirected graphs, since they are the simpler case, but every idea (degree, paths, connectivity, traversal) extends to directed graphs with small adjustments.

Weighted Graphs

An edge can carry a number describing "how much" that connection costs — distance in kilometres, travel time in minutes, or fare in rupees. A graph whose edges carry such numbers is a weighted graph; otherwise it is unweighted. Our metro graph above is weighted, using distance in km as the weight on each edge.

Weights let us ask sharper questions than "are these connected?" — for instance, "what is the total distance if I travel A → D → E → F?" We simply add the weights along the path: 2.0 + 1.5 + 3.0 = 6.5 km. Compare that with the route A → B → C → F: 3.5 + 1.8 + 2.5 = 7.8 km. Both routes use exactly three track segments, but one is 1.3 km shorter — a fact you cannot see just by counting segments. Hold onto this observation; it becomes important later in this chapter.

Degree of a Vertex, and the Handshake Rule

The degree of a vertex is simply the number of edges touching it — in an undirected graph, the number of direct neighbours it has. In our metro graph:

• deg(A) = 2  (connects to B, D)
• deg(B) = 3  (connects to A, C, E)
• deg(C) = 2  (connects to B, F)
• deg(D) = 2  (connects to A, E)
• deg(E) = 3  (connects to B, D, F)
• deg(F) = 2  (connects to C, E)

Add these up: 2 + 3 + 2 + 2 + 3 + 2 = 14. Notice that |E| = 7, and 14 is exactly twice that. This is not a coincidence — it is a general fact called the Handshake Lemma: the sum of all vertex degrees in a graph always equals twice the number of edges. The reasoning is simple once you see it: every single edge has exactly two endpoints, so when you total up degrees by walking around every vertex and counting its edges, you count each edge exactly twice — once from each end. This gives you a fast way to sanity-check any graph you draw or any adjacency data you're handed: if the degree sum is odd, something in the data is wrong, because it's mathematically impossible for a real graph.

Common Misconception: "The Drawing Is the Graph"

Here is a mistake almost every beginner makes at least once: believing that if two drawings look different, they must be different graphs, or that if two drawings look the same shape, they must be the same graph. Neither is true. A graph is defined entirely by its vertex set and edge set — not by where you happen to place dots on paper, not by which lines cross which, and not by how long you draw an edge.

Go back to the metro map at the start of this chapter: the physical layout of Delhi has almost nothing to do with how the map is drawn, yet it is still an entirely accurate graph, because every direct connection listed by the real network appears as an edge on the map. You could redraw our six-station graph as a straight line, a circle, or a scribble, and as long as A is still joined to exactly B and D, B is still joined to exactly A, C, and E, and so on, it is precisely the same graph. What must never change are the connections; what is completely free to change is the picture. When you check whether two graphs are "the same," always compare vertex sets and edge sets — never compare pictures by eye.

Representing a Graph in Code

To use a graph in a program, we need to store "which vertices connect to which" in a data structure. Two standard choices:

1. Adjacency list — for every vertex, store the list of its direct neighbours. This is usually implemented with a dictionary (hash map) in Python:

metro = {
    "A": ["B", "D"],
    "B": ["A", "C", "E"],
    "C": ["B", "F"],
    "D": ["A", "E"],
    "E": ["B", "D", "F"],
    "F": ["C", "E"]
}

# Degree of a vertex is just the length of its list
print(len(metro["B"]))   # Output: 3

Adjacency lists are memory-efficient when a graph is sparse — meaning most pairs of vertices are NOT directly connected, which is true of almost every real network (a metro station connects to a handful of others, not to every other station on the network).

2. Adjacency matrix — a grid of size |V| × |V|, where a 1 (or the weight) at row i, column j means vertex i connects to vertex j, and 0 means it doesn't:

vertices = ["A", "B", "C", "D", "E", "F"]
idx = {v: i for i, v in enumerate(vertices)}

# 6x6 grid, all zeros to start
matrix = [[0] * 6 for _ in range(6)]

edges = [("A","B"), ("A","D"), ("B","C"),
         ("B","E"), ("C","F"), ("D","E"), ("E","F")]

for u, v in edges:
    matrix[idx[u]][idx[v]] = 1
    matrix[idx[v]][idx[u]] = 1   # undirected: set both directions

for row in matrix:
    print(row)

# Output:
# [0, 1, 0, 1, 0, 0]   <- A: connects to B, D
# [1, 0, 1, 0, 1, 0]   <- B: connects to A, C, E
# [0, 1, 0, 0, 0, 1]   <- C: connects to B, F
# [1, 0, 0, 0, 1, 0]   <- D: connects to A, E
# [0, 1, 0, 1, 0, 1]   <- E: connects to B, D, F
# [0, 0, 1, 0, 1, 0]   <- F: connects to C, E

Notice the matrix is symmetric across its diagonal (row A, column B equals row B, column A) — that's exactly what "undirected" means in matrix form. For a directed graph, you would set only matrix[idx[u]][idx[v]] = 1, and the matrix would generally not be symmetric. Adjacency matrices make "are these two vertices connected?" a single lookup — O(1) time — but they waste memory on sparse graphs, since most entries sit at 0. For a graph with hundreds of thousands of vertices (like a real social network), an adjacency list is almost always the practical choice.

Paths, Walks, and Cycles

A walk is any sequence of vertices where each consecutive pair is joined by an edge — you're allowed to revisit vertices or reuse edges. A path is a stricter walk that never revisits a vertex. A cycle is a path that returns to its starting vertex, using at least three distinct vertices along the way (in an undirected simple graph).

In our metro graph, A–B–C–F is a path (three edges, four distinct vertices, valid route). A–B–E–D–A is a cycle (it returns to A, and B, E, D are all distinct from each other and from A). A–B–A–D is a walk but not a path, since vertex A is repeated.

A graph with no cycles at all, where every pair of vertices is joined by exactly one path, has a special name you may already know: a tree. Every tree is a graph, but not every graph is a tree — our metro graph, for instance, is not a tree, because it contains the cycle A–B–E–D–A. Real metro networks are deliberately built with cycles (redundant loops), because a tree-shaped network would mean a single track failure cuts off part of the city entirely; a cycle gives passengers an alternate route.

Connected Graphs

A graph is connected if there is a path between every pair of vertices — you can get from anywhere to anywhere else, possibly via intermediate stops. Our example graph is connected: you can reach F from A (via B–C or via D–E), reach D from C, and so on for every pair.

A graph is disconnected if it splits into two or more pieces with no edges between them. This happens in real life more often than you'd think: when a metro system opens two lines before the corridor joining them is built, those two lines form a disconnected graph — you could ride within one line or within the other, but no sequence of direct track segments would carry you from one to the other; you had to leave the metro system to bridge the gap. Each disconnected piece is called a connected component.

Finding the Shortest Route: Breadth-First Search

Suppose you're standing at station A and want to know, for every other station, the minimum number of stops needed to reach it (ignore distance for a moment — just count of track segments). The systematic way to answer this is an algorithm called Breadth-First Search (BFS).

The idea: explore the graph in expanding "rings," like ripples spreading outward from a stone dropped in water. First visit every station exactly one stop from A. Then, from those, visit every new station exactly two stops from A. Then three stops, and so on — never jumping ahead to a farther ring before finishing the current one. A queue (first-in, first-out) is the natural data structure for this, because it processes vertices in the exact order they were discovered.

from collections import deque

def bfs_hops(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        current = queue.popleft()
        for neighbour in graph[current]:
            if neighbour not in dist:
                dist[neighbour] = dist[current] + 1
                queue.append(neighbour)
    return dist

print(bfs_hops(metro, "A"))
# Output: {'A': 0, 'B': 1, 'D': 1, 'C': 2, 'E': 2, 'F': 3}

Let's trace this by hand to see exactly why that output is correct:

1. Start: dist = {A: 0}. Queue = [A].
2. Pop A. Neighbours of A are B, D — neither visited yet. Set dist[B] = 1, dist[D] = 1. Queue = [B, D].
3. Pop B. Neighbours of B are A (visited), C, E. Set dist[C] = 2, dist[E] = 2. Queue = [D, C, E].
4. Pop D. Neighbours of D are A (visited), E (already has dist 2 — skip, don't overwrite). Queue = [C, E].
5. Pop C. Neighbours of C are B (visited), F. Set dist[F] = 3. Queue = [E, F].
6. Pop E. Neighbours of E are B, D, F — all already visited. Nothing new. Queue = [F].
7. Pop F. Neighbours of F are C, E — both visited. Queue empty. Done.

Final result: A is 0 hops from itself, B and D are 1 hop away, C and E are 2 hops away, and F is 3 hops away — matching the printed output exactly.

A Second Misconception: "Fewest Stops" Is Not the Same as "Shortest Distance"

Look closely at the trace above. When BFS reached F, it arrived via C (F's dist was set while processing C), which means BFS's 3-hop route to F is A → B → C → F. Add up the real distances on that route from our weighted graph: 3.5 + 1.8 + 2.5 = 7.8 km.

But earlier in this chapter, we calculated a different 3-hop route, A → D → E → F, with total distance 2.0 + 1.5 + 3.0 = 6.5 km — 1.3 km shorter, despite using the exact same number of track segments (three). Plain BFS, as written above, completely ignores edge weights; it only counts hops, and it happened to discover F through C simply because of the order neighbours were listed in the adjacency dictionary, not because that route is genuinely shorter in distance.

This is a genuinely important distinction, and it is where many students go wrong: "fewest stations" and "shortest distance" are different questions with potentially different answers. BFS correctly answers the first question but not necessarily the second. Answering the weighted version — truly finding the minimum-distance route in a graph where edges carry different costs — needs an upgraded algorithm (Dijkstra's algorithm, which you'll meet in a later chapter); BFS by itself is only correct for unweighted graphs, or for weighted graphs where every edge happens to carry the same weight.

Where This Connects

Graphs are the umbrella structure behind topics you'll meet later in your CBSE Computer Science / Informatics Practices track: a tree is a connected, cycle-free graph; a linked list is a very restricted graph where every vertex has at most one outgoing edge; and shortest-path algorithms like Dijkstra's build directly on the BFS idea introduced here, upgrading a plain queue into a priority queue that respects weights. Beyond the syllabus, graphs are literally how India's largest technology systems are modelled internally — IRCTC's train-route planning, UPI's payment-routing between banks, and Google Maps' turn-by-turn directions are all, underneath their interfaces, weighted graph problems being solved thousands of times per second. Understanding vertices, edges, degree, connectivity, and traversal isn't just exam vocabulary — it's the mental model those systems are quietly built on.

Check Yourself

1. A graph has 5 vertices with degrees 2, 3, 1, 4, 2. Without drawing it, can this degree sequence belong to a real graph? Why or why not?
2. Is a WhatsApp group's "member list" better modelled as a directed or undirected graph if the question is "who can see whose messages"? What about "who has muted whom"?
3. Using the metro graph in this chapter, write out one path and one cycle that both start at vertex E, and explain which one qualifies as which and why.
4. Run BFS by hand starting from vertex F instead of A. What is the hop-distance from F to A? Does it match the hop-distance you'd get running BFS from A to F? (Think about why undirected graphs guarantee this.)
5. Explain in one or two sentences why an adjacency matrix for the entire Indian Railways network (roughly 7,500 stations) would be a poor choice of data structure, while an adjacency list would not.

Answer hints: (1) Sum the degrees — 2+3+1+4+2 = 12, which is even, so it passes the Handshake Lemma check; a graph with this exact degree sequence can be constructed. (2) "Who can see whose messages" is undirected in a WhatsApp group (all members see all messages equally); "who has muted whom" is directed, since muting is a personal, one-directional setting. (4) Yes, they must match — this holds for any undirected graph, since if a path of length k exists from A to F, walking it backwards is a valid path of length k from F to A. (5) A 7,500 × 7,500 matrix has over 56 million cells, almost all zero, since each station connects to only a handful of neighbouring stations — an enormous, mostly wasted amount of memory compared to a list that stores only real connections.

Summary

A graph G = (V, E) is a set of vertices joined by edges, and it captures connection structure while deliberately discarding geometric detail — the picture is never the graph; only the vertex set and edge set define it. Edges can be undirected (mutual, like WhatsApp contacts) or directed (one-way, like an Instagram follow), and can optionally carry weights representing cost, distance, or time. A vertex's degree counts its edges, and the Handshake Lemma guarantees the sum of all degrees in any graph equals exactly twice the edge count — a fast, reliable way to catch invalid data. Graphs are stored in code as adjacency lists (efficient for the sparse, large networks most real systems actually have) or adjacency matrices (fast lookups, but wasteful in memory at scale). Paths never repeat a vertex, walks may, and cycles return to their start; a connected graph offers a path between every pair of vertices, while a tree is the special case of a connected graph with no cycles at all. Breadth-First Search finds the minimum number of edges between a start vertex and every other vertex by exploring outward in expanding layers using a queue — but, critically, it optimises hop count, not real-world weighted distance, and mixing up those two questions is one of the most common errors when moving from theory to a real routing problem.