Introduction to Graph Theory

In graph theory, a graph is not a curve on axes: it’s a set of dots joined by lines. That simple picture can model a road map, a subway network, an electrical circuit, a group of friends, or links between web pages. This page sets up the vocabulary you’ll use for the rest of the IB graph theory topics, from adjacency matrices to route-finding algorithms.

Key ideas

Vertices, edges and adjacency

A graph is made of vertices (the dots, also called nodes) and edges (the lines joining them). Only the connections matter: you can move the vertices around or bend the edges and it’s still the same graph.

Two vertices are adjacent if an edge joins them.
Two edges are adjacent if they share a vertex.
A loop is an edge that joins a vertex to itself. Multiple edges are two or more edges joining the same pair of vertices.

An undirected graph (left) and a directed graph (right).

Degree and the handshake lemma

The degree of a vertex is the number of edges that meet there. A loop adds $2$ to the degree, because both of its ends meet the vertex. A vertex is odd or even according to its degree.

Every edge has two ends, so it adds $1$ to the degree of each of two vertices (or $2$ to one vertex, for a loop). That gives the handshake lemma:

\text{sum of all the degrees} = 2 \times \text{number of edges}

Two consequences: the sum of the degrees is always even, and so the number of odd vertices is always even.

Types of graph

Term	Meaning
Simple graph	No loops and no multiple edges
Connected graph	You can get from any vertex to any other along edges
Complete graph $K_n$	A simple graph on $n$ vertices where every pair of vertices is joined by an edge
Weighted graph	Each edge has a number (weight): a distance, cost or time
Directed graph	Each edge (often called an arc) has a direction, shown by an arrow

In $K_n$ each vertex is joined to the other $n - 1$ vertices, so it has degree $n - 1$ . Counting the ends of the edges gives $n(n - 1)$ , and each edge has been counted twice, so

\text{number of edges in } K_n = \frac{n(n - 1)}{2}

Directed graphs: in-degree and out-degree

In a directed graph, the in-degree of a vertex is the number of arcs pointing into it, and the out-degree is the number pointing out of it. Every arc leaves one vertex and enters one vertex, so

\text{sum of in-degrees} = \text{sum of out-degrees} = \text{number of arcs}

A directed graph is strongly connected if you can travel from every vertex to every other vertex following the arrows. A directed graph can be connected (if you ignore the arrows) without being strongly connected.

Subgraphs and trees

A subgraph of $G$ is a graph made from some of the vertices and some of the edges of $G$ (every edge you keep must have both its vertices kept).

A tree is a connected graph with no cycles (no closed loops). A tree with $n$ vertices always has exactly $n - 1$ edges. Remove any edge and it falls apart into two pieces; add any edge and you create a cycle. A tree that is a subgraph of $G$ and includes every vertex of $G$ is a spanning tree, the idea behind minimum spanning trees.

K_4

has

\tfrac{4 \times 3}{2} = 6

edges and

K_5

has

\tfrac{5 \times 4}{2} = 10

; a tree with

6

vertices has

5

edges.

Modelling with graphs

To model a real situation, decide what the vertices are (towns, stations, components, people) and what the edges are (roads, track, wires, friendships). Use a weighted graph if distances, costs or times matter, and a directed graph if movement is one-way (one-way streets, links from one web page to another).

Worked examples

Example 1: Degrees and adjacency

For the undirected graph in the first figure (vertices A to E):

(a) Write down the degree of each vertex and check the handshake lemma.
(b) List the vertices adjacent to B, and the edges adjacent to edge BD.

Solution. (a) Count the edges at each vertex:

Vertex	A	B	C	D	E
Degree	2	3	3	3	1

The sum is $2 + 3 + 3 + 3 + 1 = 12$ , and there are $6$ edges (AB, AC, BC, BD, CD, DE). Check: $12 = 2 \times 6$ .

(b) B is joined to A, C and D, so those are the vertices adjacent to B. The edges adjacent to BD share a vertex with it: AB and BC (at B), and CD and DE (at D).

Example 2: Using the handshake lemma

(a) Can a graph have vertices with degrees $3, 3, 2, 2, 1$ ?
(b) A graph has $7$ vertices, each of degree $4$ . How many edges does it have?

Solution. (a) The degrees add to $3 + 3 + 2 + 2 + 1 = 11$ , which is odd. The sum of the degrees must be even (twice the number of edges), so no such graph exists. Another way to see it: there are three odd vertices, and the number of odd vertices must be even.

(b) The sum of the degrees is $7 \times 4 = 28$ , so the number of edges is $\dfrac{28}{2} = 14$ .

Example 3: Complete graphs

(a) In a round-robin tournament, each of $12$ teams plays every other team once. How many games are played?
(b) A different league has $45$ games, with every team playing every other team once. How many teams are there?

Solution. (a) Model teams as vertices and games as edges. Every pair plays, so the graph is $K_{12}$ :

\frac{12 \times 11}{2} = 66 \text{ games}

(b) Solve $\dfrac{n(n - 1)}{2} = 45$ :

n(n - 1) = 90 \quad\Rightarrow\quad n^2 - n - 90 = 0 \quad\Rightarrow\quad (n - 10)(n + 9) = 0

Since $n \gt 0$ , there are $n = 10$ teams. Check: $\tfrac{10 \times 9}{2} = 45$ .

Example 4: A directed graph

For the directed graph in the first figure (vertices P, Q, R, S):

(a) Find the in-degree and out-degree of each vertex.
(b) Is the graph strongly connected?

Solution. (a) The arcs are P to Q, Q to R, R to S, S to P and P to R.

Vertex	P	Q	R	S
In-degree	1	1	2	1
Out-degree	2	1	1	1

Check: both rows add to $5$ , the number of arcs.

(b) Following the arrows, P to Q to R to S to P is a closed route through every vertex. So from any vertex you can reach any other by going around this loop: the graph is strongly connected.

Common mistakes

Counting a loop as 1 toward the degree. A loop meets its vertex twice, so it adds $2$ . That’s what keeps the handshake lemma true.

Forgetting to halve. The sum of the degrees counts every edge twice. Edges $= \tfrac{1}{2} \times$ (sum of degrees), and $K_n$ has $\tfrac{n(n - 1)}{2}$ edges, not $n(n - 1)$ or $n^2$ .

Mixing up in-degree and out-degree. In-degree counts arrows arriving at the vertex; out-degree counts arrows leaving. Check that both totals equal the number of arcs.

Assuming connected means strongly connected. In a directed graph, a vertex might be reachable only one way. Strongly connected means every vertex can reach every other along the arrows.

Calling any connected graph a tree. A tree must have no cycles. A quick test: a connected graph with $n$ vertices is a tree exactly when it has $n - 1$ edges.

Thinking the drawing matters. Edges that cross on paper don’t meet at a vertex unless a vertex is drawn there, and the lengths of edges in a drawing mean nothing unless the graph is weighted.

Practice

1. (Warm-up) A graph has vertices P, Q, R, S, T and edges PQ, PR, PS, QR, RS and ST. Find the degree of each vertex and check the handshake lemma.

Solution

P: $3$ (PQ, PR, PS). Q: $2$ . R: $3$ (PR, QR, RS). S: $3$ (PS, RS, ST). T: $1$ .

The sum is $3 + 2 + 3 + 3 + 1 = 12 = 2 \times 6$ , and there are $6$ edges.

2. (Warm-up) How many edges does $K_7$ have? What is the degree of each vertex?

Solution

\frac{7 \times 6}{2} = 21 \text{ edges}

Each vertex is joined to the other $6$ vertices, so each has degree $6$ .

3. (Warm-up) A graph has a loop at vertex A and two separate edges joining B and C. Is it a simple graph? Explain.

Solution

No. A simple graph has no loops and no multiple edges, and this graph has both: the loop at A, and the two edges between B and C.

4. (Core) A graph has $9$ edges and six vertices with degrees $2, 2, 3, 3, 4$ and $x$ . Find $x$ .

Solution

By the handshake lemma, the degrees add to $2 \times 9 = 18$ :

2 + 2 + 3 + 3 + 4 + x = 18 \quad\Rightarrow\quad 14 + x = 18 \quad\Rightarrow\quad x = 4

5. (Core) A directed graph has arcs A to B, B to C, C to A, C to D, D to E and E to D.

(a) Find the in-degree and out-degree of each vertex.
(b) Is the graph strongly connected? Explain.

Solution

(a)

Vertex	A	B	C	D	E
In-degree	1	1	1	2	1
Out-degree	1	1	2	1	1

Both rows add to $6$ , the number of arcs.

(b) No. From D the only arc goes to E, and from E the only arc goes back to D. So starting at D (or E) you can never reach A, B or C. (The graph is connected if you ignore the arrows, but not strongly connected.)

6. (Core) A complete graph has $105$ edges. How many vertices does it have, and what is the degree of each vertex?

Solution

\frac{n(n - 1)}{2} = 105 \quad\Rightarrow\quad n^2 - n - 210 = 0 \quad\Rightarrow\quad (n - 15)(n + 14) = 0

So $n = 15$ vertices, each of degree $15 - 1 = 14$ . Check: $\tfrac{15 \times 14}{2} = 105$ .

7. (Core) Use the undirected graph in the first figure (vertices A to E, edges AB, AC, BC, BD, CD, DE).

(a) Is the subgraph with vertices B, C, D and edges BC, BD, CD a tree? Explain.
(b) Write down a spanning tree of the graph, and say how many edges it has.

Solution

(a) No. Its edges form a cycle, B to C to D to B, and a tree has no cycles. (It also has $3$ vertices and $3$ edges, but a tree on $3$ vertices has $2$ edges.)

(b) One answer: the edges AB, BC, CD and DE. They include all five vertices, they’re connected, and there’s no cycle. Any spanning tree of a graph with $5$ vertices has $5 - 1 = 4$ edges. (Other answers are possible, for example AC, BC, CD, DE.)

8. (Challenge) Explain why there is no simple graph with six vertices whose degrees are $5, 5, 5, 3, 2, 2$ , even though the degrees add to an even number.

Solution

The sum is $22$ , which is even, so the handshake lemma doesn’t rule it out. But in a simple graph with six vertices, a vertex of degree $5$ is joined to all the other five vertices. With three vertices of degree $5$ , every other vertex is joined to each of those three, so every vertex has degree at least $3$ . That contradicts the two vertices of degree $2$ , so no such simple graph exists.

9. (Challenge) Prove that in any graph the number of odd vertices is even.

Solution

By the handshake lemma, the sum of all the degrees is $2 \times$ (number of edges), which is even. Split the sum into the even vertices and the odd vertices. The total from the even vertices is even, so the total from the odd vertices must also be even (even minus even is even). A sum of odd numbers is even only when there is an even number of them. So the number of odd vertices is even.