What Is a Graph?

Think of your friends and who-knows-whom. Draw a dot for each person and a line between any two who are friends. That picture — dots and lines — is a graph, and it is one of the most useful objects in all of mathematics. The same picture models a road map (towns joined by roads), the internet (computers joined by cables), a molecule (atoms joined by bonds), and a family tree. Wherever "things" are "connected", a graph is hiding.

The remarkable thing is that a graph forgets everything except the connections. It does not care where you draw the dots, how long the lines are, or whether they curve — only who is joined to whom. That ruthless simplicity is exactly what makes graphs so powerful: one idea, one picture, a thousand different worlds.

The formal definition

A graph is built from two sets. Strip away the pretty drawing and here is all a graph really is:

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

V is a set of vertices (also called nodes) — the dots;
E is a set of edges — each edge is an unordered pair of vertices \{u, v\}, drawn as a line joining them.

For example, V = \{A, B, C, D, E\} and E = \{\, \{A,B\},\ \{B,C\},\ \{C,D\},\ \{D,E\},\ \{E,A\},\ \{A,C\} \,\}. That is five vertices and six edges — a complete description, no picture required. Because an edge is an unordered pair, \{A,B\} and \{B,A\} are the same edge: this is an undirected graph, the kind we study here.

See it move

Here is that exact graph. Step through: first the edges appear, then each vertex is labelled with its degree — the number of edges touching it — and finally we add those degrees up. Watch what number comes out.

The vertices themselves can sit anywhere — drag the whole picture in your mind, stretch the lines — and it is still the same graph, because the set of edges has not changed.

Degree: how connected is a vertex?

The degree of a vertex, written \deg(v), is simply the number of edges meeting it. In the graph above, \deg(A) = 3 (edges to B, E and C), while \deg(B) = 2. A vertex of degree 0 is isolated — a lonely dot with no lines at all.

Degree is a first, cheap measure of importance. In a social network, high-degree people are the connectors; in a road map, a high-degree town is a busy junction. And once you can count degrees, a beautiful, unbreakable law appears.

The Handshake Lemma

Add up the degrees of every vertex and you always get the same magic answer: twice the number of edges.

For any graph G = (V, E):

the sum of all vertex degrees equals twice the number of edges, \displaystyle \sum_{v \in V} \deg(v) = 2\,|E|;
consequently the number of odd-degree vertices is always even.

Why is it true? Look at any single edge, say \{A, B\}. It has two endpoints, so it adds 1 to \deg(A) and 1 to \deg(B) — a total of 2 to the grand sum of degrees. Every edge does this, contributing exactly 2. So the whole sum is 2 for each edge: 2\,|E|. No counting of the actual graph needed — it must come out even.

Check it on our example: the degrees are 3 + 2 + 3 + 2 + 2 = 12, and indeed 12 = 2 \times 6 = 2\,|E|. The two odd-degree vertices (A and C, both degree 3) come in a matched pair — never a lone odd one out.

Picture a party where some people shake hands. Make a graph: a vertex per guest, an edge per handshake. A guest's degree is how many hands they shook. Every handshake involves exactly two hands, so when you total everyone's tally you have counted each handshake twice — the sum of degrees is 2 \times (\text{number of handshakes}).

The punchline: the number of people who shook an odd number of hands is always even. You can walk into any room in the world, and this is guaranteed true without counting a thing. That is the quiet power of a proof.

Simple graphs vs. multigraphs

Our first example was a simple graph: at most one edge between any two vertices, and no edge from a vertex back to itself. Most of the time "graph" means "simple graph". But two other creatures are allowed if we relax the rules:

a loop — an edge from a vertex to itself (it adds 2 to that vertex's degree, since both endpoints are the same vertex);
parallel edges — two or more edges joining the same pair of vertices.

A graph that permits loops or parallel edges is a multigraph. The Handshake Lemma still holds for multigraphs — every edge, loop and all, contributes exactly 2 to the sum of degrees.

In earlier maths you drew "graphs" like y = x^2 — a curve on x-y axes. That is the graph of a function, and it is a completely different meaning of the word. It shares the name only by historical accident.

A graph-theory graph has no axes, no coordinates, and no notion of distance. It is just dots and connections. When you place the dots on a page you may put them anywhere — the maths does not change. So when someone says "graph", check which world you are in: a plotted curve, or a network of vertices and edges. On this page — and in all of graph theory — it always means the latter.

A graph as data

Because a graph is two sets, a computer stores it directly. Here we list the edges, count how many touch each vertex to get the degrees, and confirm the Handshake Lemma — the sum of degrees comes out to twice the edge count. Press Run.

const V = ["A", "B", "C", "D", "E"]; const E: [string, string][] = [ ["A", "B"], ["B", "C"], ["C", "D"], ["D", "E"], ["E", "A"], ["A", "C"], ]; const degree: Record<string, number> = {}; for (const v of V) degree[v] = 0; for (const [a, b] of E) { degree[a]++; degree[b]++; } let sum = 0; for (const v of V) sum += degree[v]; console.log("degrees:", degree); console.log("sum of degrees =", sum); console.log("2 x (number of edges) =", 2 * E.length);