Introduction to Graphs: Networks and Connections

Open the metro app in any Indian city and ask it for directions between two stations you've never heard of. In less than a second it tells you: take the Blue Line, change at a particular interchange, take the Yellow Line, get off after five stops. It did this without "seeing" a map the way you do. It didn't measure distances on a picture. It worked with a list of stations and a list of which stations connect directly to which other stations — nothing else. That list-of-connections structure is called a graph, and it is one of the most useful ideas in all of computer science. It is also hiding behind Instagram's "people you may know," Google Maps' fastest-route calculation, the internet's routers deciding where to send your data, and even the CBSE syllabus map that groups chapters by prerequisite. This chapter builds the idea of a graph from scratch, shows you the two standard ways a computer stores one in memory, and gives you enough vocabulary to read any graph-related problem you'll meet from here through competitive programming.

From a Messy Map to a Clean Structure

Imagine five Indian cities that have direct flights between some pairs of them: Delhi (DEL), Mumbai (BOM), Bengaluru (BLR), Chennai (MAA), and Kolkata (CCU). Suppose the direct flight routes are: Delhi–Mumbai, Delhi–Bengaluru, Mumbai–Chennai, Bengaluru–Chennai, and Bengaluru–Kolkata. If you drew this as a picture, you'd put a dot for each city and a line for each direct flight. Strip away everything else — the actual geography, the flight numbers, the airline names — and what's left is exactly a graph: a set of things (the cities) and a set of connections between pairs of them (the direct flights).

Here is that exact network drawn out:

Formally, a graph is written as G = (V, E): a set of vertices (also called nodes) V, and a set of edges E, where each edge connects a pair of vertices. In our flight network, V = {DEL, BOM, BLR, MAA, CCU} and E has 5 edges: {DEL–BOM, DEL–BLR, BOM–MAA, BLR–MAA, BLR–CCU}. When an edge connects two vertices, we say those vertices are adjacent, or that they are each other's neighbors. Bengaluru and Chennai are neighbors because there's a direct flight; Delhi and Kolkata are not, because you'd need to change planes.

Two Kinds of Connections: Directed vs Undirected

The flight-route graph above is an undirected graph — an edge between BLR and MAA means you can fly Bengaluru→Chennai and Chennai→Bengaluru on the same route. The connection has no direction; it's symmetric by nature.

Not every real network works this way. Think about who follows whom on Instagram. If Aarav follows Priya, that tells you nothing about whether Priya follows Aarav back — those are two separate, independent facts. A graph that models this needs directed edges (also called arcs): an edge from A to B is not automatically an edge from B to A. We draw a directed edge as an arrow, and the whole structure is called a directed graph, or digraph for short.

Read the arrows carefully: Aarav → Priya (Aarav follows Priya), Priya → Meera (Priya follows Meera), Meera → Priya (Meera follows Priya back), and Meera → Aarav (Meera follows Aarav). Notice that Priya and Meera have a mutual connection — two arrows, one in each direction — while Aarav follows Priya but Priya does not follow Aarav back. Both situations are perfectly normal in a directed graph. This is exactly the misconception worth naming directly: students often assume every graph edge must work both ways, because the undirected examples (roads, mutual friendships) come first and feel "default." But direction is a real, independent property of a graph — road networks with one-way streets, hyperlinks on the web (page A can link to page B without B linking back), and "follows" relationships are all naturally directed, and treating them as undirected would produce wrong answers.

Directed graphs also split the idea of "degree" into two counts: in-degree (how many arrows point into a vertex) and out-degree (how many arrows point out of it). In the follow-network above, Priya has in-degree 2 (followed by Aarav and Meera) and out-degree 1 (follows only Meera) — she has more followers than people she follows, exactly the number you'd see on a real profile.

Weighted Graphs: When a Connection Has a Cost

So far every edge has meant the same thing — "connected" or "not connected." Real networks usually attach a number to each edge too. A road network's edges carry distance in kilometres; a flight network's edges carry price or duration; a computer network's edges carry latency in milliseconds. A graph where every edge carries a number like this is called a weighted graph, and the number is the edge's weight. If our flight graph were weighted by flight duration, the DEL–BLR edge might carry the label "2h 45m" while DEL–BOM carries "2h 10m." Weighted graphs matter because "shortest path" then means "least total weight," not just "fewest edges" — a distinction Google Maps' "fastest route" (weighted by time) versus "fewest turns" (unweighted, roughly) makes every day. This chapter mostly works with unweighted graphs to keep the fundamentals clear; weighted-graph algorithms like Dijkstra's are built on top of exactly the structure introduced here.

Vocabulary: Degree, Path, Cycle, and Connectedness

A few more terms, all illustrated by the flight-network graph:

• Degree of a vertex (undirected graph) — the number of edges touching it. Bengaluru (BLR) has degree 3: it connects to Delhi, Chennai, and Kolkata. Kolkata (CCU) has degree 1: it connects only to Bengaluru.
• Path — a sequence of vertices where each consecutive pair is joined by an edge, with no vertex repeated. DEL → BLR → CCU is a path of length 2 (two edges) from Delhi to Kolkata.
• Cycle — a path that starts and ends at the same vertex, using at least three distinct vertices along the way. DEL → BOM → MAA → BLR → DEL is a cycle: it returns to Delhi after visiting four different cities using four edges.
• Connected graph — a graph where a path exists between every pair of vertices. Our flight network is connected: you can reach any of the five cities from any other, possibly with a stop. If Kolkata had no flights at all, the graph would be disconnected, and Kolkata would sit in its own isolated piece.

Storing a Graph Inside a Computer: The Adjacency Matrix

A picture is fine for a human, but a program needs numbers and arrays. The most direct way to store a graph is an adjacency matrix: a grid with one row and one column per vertex, where cell (row i, column j) holds 1 if vertex i and vertex j are connected by an edge, and 0 if they are not.

For our 5-city flight network, ordering the vertices as DEL, BOM, BLR, MAA, CCU, the matrix looks like this:

Check the row for BLR: it reads 1, 0, 0, 1, 1 — meaning Bengaluru connects to DEL, MAA, and CCU, but not to itself (a vertex is never adjacent to itself, so the diagonal is always 0) or to BOM (no direct BOM–BLR flight in our list). That row-sum of 3 is exactly the degree we calculated earlier for BLR.

Now count the whole grid. There are 5 vertices, so the matrix has 5 × 5 = 25 cells in total. Counting the 1s row by row: DEL has 2, BOM has 2, BLR has 3, MAA has 2, CCU has 1. That's 2 + 2 + 3 + 2 + 1 = 10 cells containing 1, which means the remaining 25 − 10 = 15 cells contain 0 — 60% of the matrix is empty even in this reasonably well-connected 5-city network. This isn't a coincidence: in an undirected graph, every single edge fills in two cells (once for row A/column B, once for row B/column A), so the count of 1s is always exactly 2 × (number of edges) = 2 × 5 = 10 here. As the number of cities grows into the thousands — real flight networks, real road networks, real social networks — the matrix keeps growing as (number of vertices)², while the number of real connections grows much more slowly, so the fraction of zeros climbs toward 100%. Storing a nearly-empty grid wastes enormous amounts of memory, which motivates the second representation.

The Space-Efficient Alternative: The Adjacency List

An adjacency list stores, for each vertex, just the list of its actual neighbors — no wasted cells for pairs that aren't connected. In Python, a natural way to write this is a dictionary mapping each city to a list of its neighboring cities:

flights = {
    "DEL": ["BOM", "BLR"],
    "BOM": ["DEL", "MAA"],
    "BLR": ["DEL", "MAA", "CCU"],
    "MAA": ["BOM", "BLR"],
    "CCU": ["BLR"]
}

for city in flights:
    print(city, "connects to", len(flights[city]), "cities:", flights[city])

Tracing this line by line: the loop visits each key of the dictionary in insertion order (DEL, BOM, BLR, MAA, CCU) and prints its neighbor list and count. The output is:

DEL connects to 2 cities: ['BOM', 'BLR']
BOM connects to 2 cities: ['DEL', 'MAA']
BLR connects to 3 cities: ['DEL', 'MAA', 'CCU']
MAA connects to 2 cities: ['BOM', 'BLR']
CCU connects to 1 cities: ['BLR']

These counts — 2, 2, 3, 2, 1 — are exactly the degrees we found from the matrix rows, confirming the two representations agree; they're just different ways of storing the same information. We can even recover the total number of edges directly from the adjacency list, without ever building a matrix:

total_degree = sum(len(neighbors) for neighbors in flights.values())
print(total_degree, total_degree // 2)

Here total_degree adds up every neighbor-list length: 2 + 2 + 3 + 2 + 1 = 10. Since every edge was counted once from each of its two endpoints, dividing by 2 recovers the true edge count: 10 // 2 = 5, matching the five flight routes we started with. This "sum of degrees equals twice the number of edges" rule (sometimes called the handshake rule) is a useful sanity check any time you build a graph by hand — if your degree sum comes out odd, you've made a counting mistake somewhere, since it can never be odd for a valid undirected graph.

The trade-off between the two representations comes down to memory versus lookup speed. An adjacency matrix always uses space proportional to V² (V = number of vertices), no matter how few edges exist, but answering "is city X directly connected to city Y?" takes one instant lookup. An adjacency list uses space proportional to V + E (E = number of edges), which is far smaller for a sparse graph — one where E is much less than V² — but checking whether two specific cities are connected means scanning through a neighbor list. Real-world graphs (flight networks, social networks, road networks) are almost always sparse, which is why adjacency lists are the default choice in practice; a full India road-network graph with lakhs of intersections would need trillions of matrix cells but only a few hundred thousand list entries.

Worked Example: Finding a Route by Hand

Suppose you want the flight route from Delhi to Kolkata using the fewest stops, working only from the adjacency list, with no map in front of you. Start at DEL and look at its direct neighbors: BOM and BLR — call this "one stop away." Neither is Kolkata, so look at their neighbors in turn: BOM's neighbors are DEL (already seen) and MAA; BLR's neighbors are DEL (already seen), MAA, and CCU. CCU — Kolkata — shows up here, reached through BLR. So the shortest route is DEL → BLR → CCU, just one connecting flight, two edges total. Notice the method: explore everything one hop away first, then everything two hops away, and stop the moment you find the target. This hop-by-hop, layer-by-layer exploration has a name — Breadth-First Search — and it is exactly the family of technique that a real metro-routing app runs internally to guarantee the fewest-interchange answer; you've just done it by hand on five cities.

Common Misconceptions, Corrected

"Graph" here means the same thing as the bar graphs and line graphs from Math class. It doesn't. A bar graph plots numeric values on axes; a graph in computer science is a network of vertices and edges — there are no axes and no numbers being plotted at all (unless you separately choose to add weights). The shared English word is a historical accident, not a hint that the two ideas are related.

Every edge must connect back in both directions. False, as the follow-network showed directly — Aarav → Priya without Priya → Aarav is a completely valid directed edge. Undirected graphs (roads with two-way traffic, mutual friendships) are the special case where direction happens not to matter, not the general rule.

A tree (like a family tree or a computer's folder structure) is something separate from a graph. A tree is actually a specific, restricted kind of graph: a connected graph with no cycles, which also guarantees it has exactly (number of vertices − 1) edges. Every tree satisfies the definition G = (V, E) just like any other graph — it simply obeys an extra rule that ordinary graphs don't have to.

Check Yourself

1. In the flight network, what is the degree of BLR (Bengaluru), and which cities are its neighbors?
2. True or False: in a directed graph, if an edge A → B exists, an edge B → A must also exist. Use the Aarav/Priya/Meera example to justify your answer.
3. A new graph has 8 vertices. If you store it as an adjacency matrix, how many total cells will the matrix have?
4. That same 8-vertex graph is undirected and has exactly 6 edges. How many of the matrix's cells will contain a 1?
5. You need to represent a graph with 10,000 vertices but only about 15,000 edges. Would you choose an adjacency matrix or an adjacency list? Justify using space complexity.
6. Is a family tree a graph? Justify your answer using the formal definition G = (V, E).

Answers: (1) Degree 3; neighbors are DEL, MAA, and CCU. (2) False — Aarav → Priya exists in the diagram, but Priya → Aarav does not; only Priya↔Meera is mutual. (3) 8 × 8 = 64 cells. (4) 2 × 6 = 12 cells, since each undirected edge fills two symmetric cells in the matrix. (5) Adjacency list — a matrix would need 10,000² = 100,000,000 cells, almost all zero, while a list needs space proportional to V + E, roughly 25,000 entries here, which is dramatically smaller. (6) Yes — a family tree is a connected graph with no cycles (you can't be your own ancestor), which makes it a tree, and every tree is a graph by definition; it just carries the extra restriction of having no cycles.

Summary

A graph G = (V, E) is a set of vertices and a set of edges connecting pairs of them — the same structure underneath a metro map, a flight network, a follow-network, and the internet's routing tables. Edges can be undirected (symmetric, like roads) or directed (one-way, like follows), and can optionally carry a weight (like distance or time). Key vocabulary — degree, in-degree/out-degree, path, cycle, and connectedness — lets you describe any graph precisely. Computers store graphs two ways: an adjacency matrix (V² space, instant edge-lookup, wasteful when the graph is sparse) or an adjacency list (V + E space, the practical default for real sparse networks). Finding a shortest route by exploring one hop at a time, as we did from Delhi to Kolkata, is the seed of Breadth-First Search, one of the core graph algorithms you'll formalize next.