Dots, lines and the language of graphs

What is a graph?

In everyday speech a "graph" is usually a chart with axes, like a line showing temperature over a week. In mathematics the word means something different and much simpler.

A graph is a collection of things together with a record of which pairs of things are connected. That's it. We draw each thing as a dot and each connection as a line between two dots.

Here are six friends. A line between two people means they know each other.

From the picture you can answer questions straight away. Does Ana know Dev? No, there is no line between them. But Ana could be introduced to Dev through Ben, because Ana–Ben and Ben–Dev are both lines. Who has the fewest friends? Fay, with just one.

Written out in this notation, the friendship graph is:

V = {Ana, Ben, Cara, Dev, Eli, Fay}
E = {Ana–Ben, Ana–Cara, Ben–Cara, Ben–Dev, Cara–Eli, Dev–Eli, Eli–Fay}

So this graph has 6 vertices and 7 edges. The picture and the two lists carry exactly the same information. The picture is easier for people to read; the lists are easier to type into a computer.

Graphs are everywhere

Once you know what to look for, you see graphs all over the place. The trick is always to ask: what are the things, and what counts as a connection?

The last row is a good example of how flexible the idea is. Nothing in a Sudoku puzzle looks like dots and lines, but the rules are a graph in disguise. We'll come back to it in Unit 9.

Only the connections matter

A graph is who is connected to whom, nothing more. Where you put the dots, how long the lines are and whether they are straight or curvy are just choices about the drawing. They are not part of the graph.

Look at these two pictures. They look nothing alike, but check the edges one by one: both have exactly A–B, B–C, C–D, D–E and E–A.

In drawing 2, lines cross in the middle. Those crossing points are not vertices. They are just places where the ink happens to overlap. Vertices are only the dots we deliberately put there.

The basic vocabulary

A handful of words do most of the work in graph theory. We'll use the friendship graph from above for every example.

Endpoints

The two vertices an edge joins. The edge Ben–Dev has endpoints Ben and Dev.

Adjacent

Two vertices are adjacent if an edge joins them. Ben and Cara are adjacent; Ana and Dev are not.

Neighbours

All the vertices adjacent to a given vertex. The neighbours of Eli are Cara, Dev and Fay.

Incident

An edge is incident to the vertices at its ends. The edge Eli–Fay is incident to Eli and to Fay.

Loops and multiple edges

Sometimes it's useful to allow two odd kinds of edge:

• A loop is an edge that starts and ends at the same vertex. Think of a scenic road that leaves a town and comes back to it.
• Multiple edges (or parallel edges) are two or more edges joining the same pair of vertices. Think of two different bridges between the same two riverbanks.

Most of this course is about simple graphs, so "graph" means simple graph unless we say otherwise. Multigraphs will be important in Unit 6, where we solve a famous puzzle about seven bridges.

Degree: counting connections

The single most useful number you can attach to a vertex is how many edges touch it.

In the friendship graph, degree just means "number of friends". Hover over or tap the people in the first picture to check these values:

A few related words:

• A vertex of degree 0 is isolated: nobody is connected to it. A new member of a social network who hasn't added anyone yet.
• A vertex of degree 1 is a leaf (or pendant vertex). Fay is a leaf. Leaves will matter a lot when we study trees in Unit 3.
• The degree sequence is the list of all degrees, usually from largest to smallest. Here it is (3, 3, 3, 2, 2, 1).
• The largest degree is written Δ (capital delta) and the smallest δ (small delta). Here Δ = 3 and δ = 1.

The handshake lemma

Here is our first real theorem. It's simple, but it's used constantly.

Imagine a party. As people arrive, some of them shake hands. At the end, everyone writes down how many hands they shook, and someone adds up all the numbers. Whatever happened at the party, the total is always even. Why?

Because every handshake involves exactly two hands. Each handshake gets counted once by each of the two people, so it adds exactly 2 to the total.

The same is true for any graph. Each edge has two ends, and each end adds 1 to the degree of the vertex it touches. In the picture below, every pink dot is one "end of an edge":

Checking with our friends: 2 + 3 + 3 + 2 + 3 + 1 = 14, and 2 × 7 = 14. ✓

The odd-degree consequence

The sum of all degrees is even. Even-degree vertices add an even amount, so the odd-degree vertices together must also add up to an even number. A sum of odd numbers is only even when there's an even count of them. So:

In the friendship graph, Ben, Cara, Eli and Fay have odd degree. That's four people, an even number, as promised.

Directed graphs

Friendship goes both ways: if Ana knows Ben, Ben knows Ana. But many connections are one-way. On Instagram, you can follow someone who doesn't follow you back. A one-way street lets traffic go in only one direction. A web page can link to another that doesn't link back.

For these we use a directed graph (or digraph), where each edge has a direction, drawn as an arrow. Directed edges are often called arcs.

Now each vertex has two kinds of degree:

• The in-degree is the number of arrows coming in: here, the number of followers.
• The out-degree is the number of arrows going out: the number of accounts that person follows.

The handshake idea still works, with a twist. Every arrow has exactly one tail (where it leaves) and one head (where it arrives). So:

Weighted graphs

Sometimes a connection isn't just there or not there; it has a size. A road has a length, a flight has a price, a cable has a capacity. A weighted graph attaches a number, called a weight, to each edge.

Weights let us ask much richer questions. "Can I walk from Home to the Library?" is easy: yes. "What's the quickest way?" needs the weights. Here are three possible routes:

The direct-looking route through School isn't the fastest; the detour through the Park wins. Checking every route by hand works for a tiny town but becomes hopeless for a whole country. In Unit 5 you'll learn Dijkstra's algorithm, the idea behind every map app's "fastest route" button.

Weights and directions can combine. A map of one-way streets with travel times is a weighted directed graph. So is a table of flight prices, since flying A → B often doesn't cost the same as B → A.

Graphs worth knowing by name

Some patterns turn up so often that they have their own names and symbols. Knowing them is like knowing "square" and "triangle" in geometry.

Complete graphs: everyone connected to everyone

The complete graph K_n has n vertices with every possible edge between them.

How many edges does K_n have? Use the handshake lemma. Each of the n vertices is joined to the other n − 1, so the degrees add up to n(n − 1). Halving gives:

Other families

• A path P_n is n vertices in a row, each joined to the next. Like stops along a single bus route. It has n − 1 edges.
• A cycle C_n is a path whose ends are joined up into a ring, like seats around a round table. It has n edges and every vertex has degree 2.
• A star has one central vertex joined to all the others, and no other edges. Old-style office networks wired every computer to one central switch.
• A graph is bipartite if its vertices split into two groups so that every edge goes between the groups, never inside one. Students and the clubs they belong to form a bipartite graph: a student joins a club, but students don't "join" students. In the complete bipartite graph K_m,n every one of the m vertices on one side is joined to every one of the n on the other, giving m × n edges. Unit 7 is all about bipartite graphs.
• The empty graph has vertices but no edges at all. Not very exciting, but useful as a starting point.

Subgraphs

Often we care about only part of a graph. A subgraph is what you get by keeping some of the vertices and some of the edges, with one rule: you can only keep an edge if you also keep both its endpoints.

A group where everyone knows everyone else, like Ana, Ben and Cara, is a complete graph sitting inside a bigger graph. These groups are called cliques, just like in everyday speech. Social networks search for them to suggest groups and communities.

Writing a graph down

Pictures are great for people, but a computer needs the graph as data. There are three common ways to write one down. We'll use this small graph:

1. Edge list

Just list the edges: A–B, A–C, B–C, C–D. It's simple and compact, but slow to answer "who are C's neighbours?" because you have to read the whole list.

The adjacency matrix is a grid with one row and one column per vertex. Put a 1 where the row's vertex and the column's vertex are adjacent, and a 0 otherwise. It works like the distance chart in a road atlas, where you look up a row and a column to find the answer. Three things to notice:

• Each row adds up to the degree of that vertex (pink numbers). That's the handshake lemma hiding in a table.
• For an undirected graph the grid is symmetric: the entry for row A, column B equals the entry for row B, column A, because A–B and B–A are the same edge.
• The diagonal is all 0s, because a simple graph has no loops.

The adjacency list gives each vertex its own list of neighbours, like each person's phone contacts. It's the most common choice in real software.

Practice set

Mixed questions covering the whole unit. Try each one before opening the answer.

Summary and glossary

1. A graph is a set of vertices plus a set of edges joining pairs of them. Only the connections matter, not the drawing.
2. The degree of a vertex is the number of edges touching it.
3. Handshake lemma: the degrees add up to twice the number of edges. So the number of odd-degree vertices is always even.
4. Directed graphs have one-way arcs, with in-degree and out-degree. Weighted graphs put numbers on edges.
5. Learn the families by name: complete K_n (with n(n − 1)/2 edges), path, cycle, star, bipartite and empty graphs.
6. Computers store graphs as edge lists, adjacency matrices or adjacency lists. Each one makes different questions fast.

Graph

A set of vertices with edges joining pairs of them.

Vertex (node)

One of the "things" in a graph, drawn as a dot.

Edge (link)

A connection between two vertices, drawn as a line.

Adjacent

Joined by an edge.

Degree

The number of edges at a vertex. A loop counts twice.

Simple graph

A graph with no loops and no repeated edges.

Isomorphic

Having exactly the same pattern of connections.

Directed graph

A graph whose edges (arcs) point one way.

Weighted graph

A graph with a number on each edge.

Complete graph K_n

n vertices, every pair joined.

Bipartite

Vertices split into two groups, with edges only between the groups.

Subgraph

Some of a graph's vertices and edges, kept together.

Adjacency matrix

A grid of 0s and 1s recording which pairs are adjacent.