Graph Data Structure Explained: Nodes, Edges and Degree

A graph is the most general data structure you will meet in an interview: a set of things, plus the connections between them. Road maps, social networks, package dependencies, web links, molecules and course prerequisites are all graphs. Before BFS, DFS or Dijkstra make sense, you need the vocabulary: nodes, edges, direction, weight, degree, and the few counting facts that let you sanity-check any graph problem in seconds.

The problem it solves

Arrays and lists model order; trees model hierarchy. Many real relationships are neither:

• Friendships go both ways and form cycles.
• Dependencies go one way: a build step needs another to finish first.
• Roads have lengths, and some are one-way.
• Bonds in a molecule connect atoms with no "first" or "root" at all.

A graph models any of these with two ingredients, and the vocabulary tells you which algorithm applies. "Directed and acyclic" suggests a topological sort; "unweighted shortest path" suggests BFS; "weighted, non-negative" suggests Dijkstra.

The intuition

The words that matter:

• Node (vertex) and edge (a connection between two nodes). n or V counts nodes, m or E counts edges.
• Undirected edges work both ways, like a bond. Directed edges have an arrow, like a conveyor from cutting to welding.
• Weighted edges carry a number: a distance, a cost, a capacity.
• Degree: in an undirected graph, how many edges touch a node. In a directed graph, split into in-degree (arrows arriving) and out-degree (arrows leaving).
• Path, cycle, connected: a path is a walk along edges without repeating a node; a cycle returns to its start; a graph is connected if every node can reach every other.

Three counting facts are worth memorising:

• The handshake lemma. In an undirected graph, the degrees add up to exactly 2E, because every edge is counted once from each end. A consequence: the number of odd-degree nodes is always even.
• Maximum edges. A simple undirected graph (no self-loops, no repeated edges) has at most n(n - 1) / 2 edges. Graphs near that are dense; graphs with edges closer to n are sparse, and most real graphs are sparse, which is why the adjacency list is the default representation.
• Trees are graphs. A tree is a connected graph with no cycles, and equivalently a connected graph with exactly n - 1 edges, and equivalently a graph with exactly one path between every pair of nodes.

One modelling caution from the lesson's own example: in methanol every bond is single, so an atom's degree equals its valence. Carbon dioxide has two double bonds, and a simple graph would give carbon degree 2 when chemistry says 4. You need repeated edges (a multigraph) or an edge weight for the bond order. Deciding what an edge means is part of the design.

Watch it run

The animation draws the lesson's methanol molecule. A graph is things plus the connections between them, and that is the entire definition. Here the things are atoms, six of them: one carbon, one oxygen, four hydrogens. The connections are bonds, five of them, and they are undirected: a bond works both ways, so it has no arrow. A node's degree is simply how many edges touch it, and carbon touches four. Oxygen touches two, one bond to carbon and one to its hydrogen, so degree 2. Every hydrogen has degree 1, one bond each. Finally, the degrees sum to 4 + 2 + 1×4 = 10, and 10 / 2 = 5 bonds: every edge is counted from both ends.

The code

The lesson's molecule as an edge list turned into an adjacency list, the handshake check, in- and out-degrees on a directed conveyor, the edge ceiling, the carbon dioxide multigraph, and a tree test:

from collections import defaultdict

def undirected(edges):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)               # a bond works both ways: store it twice
    return adj

methanol = [("C", "H1"), ("C", "H2"), ("C", "H3"), ("C", "O"), ("O", "H4")]
adj = undirected(methanol)
degree = {atom: len(adj[atom]) for atom in sorted(adj)}
print(degree)
# {'C': 4, 'H1': 1, 'H2': 1, 'H3': 1, 'H4': 1, 'O': 2}
print(sum(degree.values()), 2 * len(methanol))      # 10 10

conveyor = [("cut", "weld"), ("weld", "paint"), ("cut", "paint"), ("paint", "pack")]
out_deg, in_deg = defaultdict(int), defaultdict(int)
for u, v in conveyor:                  # directed: one-way, stored once
    out_deg[u] += 1
    in_deg[v] += 1
print(dict(out_deg), dict(in_deg))
# {'cut': 2, 'weld': 1, 'paint': 1} {'weld': 1, 'paint': 2, 'pack': 1}

n = 6
print(len(methanol), "of", n * (n - 1) // 2, "possible edges")   # 5 of 15 possible edges

co2 = [("O1", "C"), ("O1", "C"), ("C", "O2"), ("C", "O2")]      # double bonds
print(len(undirected(co2)["C"]), len(set(undirected(co2)["C"])))  # 4 2

def is_tree(nodes, edges):
    """Connected, with exactly n - 1 edges (so no cycle can fit)."""
    if len(edges) != len(nodes) - 1:
        return False
    adj, seen, stack = undirected(edges), {nodes[0]}, [nodes[0]]
    while stack:
        for nxt in adj[stack.pop()]:
            if nxt not in seen:
                seen.add(nxt)
                stack.append(nxt)
    return len(seen) == len(nodes)

print(is_tree(sorted(degree), methanol), is_tree(list("abcd"), [("a", "b"), ("b", "c"), ("c", "a")]))
# True False

Carbon dioxide's carbon has four edges in the multigraph but only two distinct neighbours. Checked on 3,000 seeded random simple graphs of up to seven nodes: the handshake lemma and the even number of odd-degree nodes always hold, and is_tree agrees with a brute force that enumerates every simple path and demands exactly one between each pair:

import random
from itertools import combinations

def count_paths(adj, u, target, seen):
    """Brute force: every simple path from u to target, by trying all of them."""
    if u == target:
        return 1
    return sum(count_paths(adj, v, target, seen | {v}) for v in adj[u] if v not in seen)

rng = random.Random(32)
ok, trees = True, 0
for _ in range(3_000):
    nodes = list(range(rng.randint(1, 7)))
    pairs = list(combinations(nodes, 2))
    edges = rng.sample(pairs, rng.randint(0, len(pairs)))
    adj = undirected(edges)
    degs = [len(adj[v]) for v in nodes]
    ok &= sum(degs) == 2 * len(edges)                     # handshake lemma
    ok &= sum(d % 2 for d in degs) % 2 == 0               # odd degrees come in pairs
    brute = all(count_paths(adj, a, b, {a}) == 1 for a, b in pairs)
    ok &= is_tree(nodes, edges) == brute                  # a tree: exactly one path per pair
    trees += brute
print(ok, trees)                                          # True 848

The complexity

• Building an adjacency list from E edges: O(V + E) time and space.
• Degree of a node: O(1) with an adjacency list of lists; the sum of all degrees is O(V).
• Tree test: one traversal, O(V + E). The path-counting brute force is exponential, fine only for tiny graphs.
• Edges: anywhere from 0 to n(n - 1) / 2 in a simple undirected graph, so "O(V + E)" can mean O(V²) on a dense graph.

Where it goes wrong

• Storing an undirected edge once. Traversal then only works in one direction.
• Forgetting isolated nodes. An edge list never mentions a node with degree 0; keep the node list separately.
• Assuming connected. Many problems hide several components; loop over every node as a start.
• Mixing up simple and multigraphs. Duplicate edges break "at most n(n - 1) / 2" and inflate degrees.
• Counting edges as the sum of degrees. Halve it for undirected graphs.

When it shows up in interviews

Constantly, usually disguised: a grid, a list of prerequisites, a friend list or a set of flights is a graph once you say so. Being able to say "nodes are courses, directed edges are prerequisites, I need to detect a cycle" is half of topological sort, BFS and connected components problems. "Is this graph a valid tree?" is a common problem in its own right.

How to say it in an interview

"A graph is nodes plus edges. I first decide whether edges are directed and whether they're weighted, because that picks the algorithm. I'd store it as an adjacency list, adding undirected edges in both directions, which is O(V plus E). Degree is the number of edges at a node, and the degrees sum to twice the edge count, a quick sanity check. A valid tree is connected with exactly n minus 1 edges, so one traversal plus an edge count decides it."