3.14 · AHL · HL onlyPaper 1Paper 2Paper 3

Graph theory basics

32 min read

In a minute

A is a set of points, called , joined by lines, called . It records only what is linked to what, so it can model road maps, circuits, networks and one-way streets. Here you learn the words for describing graphs and how to turn a real situation into one.

You'll be able to

  • Describe a graph with the words vertex, edge, adjacent and , and use the fact that the degrees add up to twice the number of edges.
  • Represent a real situation, such as a road map or a circuit, as an unweighted or a .
  • Decide whether a graph is , or , and give the reason.
  • Find in-degrees and out-degrees in a , and decide whether it is .
  • Identify and , and use the fact that a tree with nn vertices has n−1n - 1 edges.
Before you start2 quick questions on what this builds on
Check yourself
Six friends meet, and each pair of friends shakes hands once. How many handshakes are there?
Check yourself
Bus times are Ashby to Brook 1212 minutes, Ashby to Corfe 2525 minutes and Brook to Corfe 1717 minutes. How long does Ashby to Brook to Corfe take?

Vertices, edges and degree

A metro map, a ferry network and an office computer network all show some places and which pairs are linked. A graph keeps only that.

A vertex (plural vertices, or node) is a point. An edge joins two vertices. An edge from a vertex back to itself is a loop. Two or more edges joining the same pair are multiple edges.

Where you draw the vertices, and how long or curved the edges are, means nothing. Edges that cross on paper don't meet unless there is a vertex there.

Two vertices are adjacent if an edge joins them. Two edges are adjacent if they share a vertex.

Learn this
∑deg⁡(V)=2×number of edges\sum \deg(V) = 2 \times \text{number of edges}

So the degrees always add to an even number.

A graph with five vertices A, B, C, D and E. Edges: A to B, A to C, B to C, B to D, two separate edges between C and D, D to E, and a loop at E. A B C D E
Trails between five huts. Two trails join C and D; a circular trail starts and ends at E.
Worked exampleFor the hut trails in the figure: (a) write down the huts adjacent to B; (b) find the degree of each hut, in the order A, B, C, D, E.

Try it first, then reveal one step at a time.

  1. (a) B's edges go to A, C and D, so these are adjacent to B.
Worked exampleAn office network has 1414 switches. Each switch is cabled directly to exactly 55 other switches, with at most one cable between any two. Find the number of cables.

Try it first, then reveal one step at a time.

  1. Each switch is a vertex of degree 55, and each cable is an edge.
Check yourself
In the hut graph, which pair of edges is adjacent?
Check yourself
A graph has 66 vertices with degrees 1,2,2,3,31, 2, 2, 3, 3 and 55. How many edges does it have?
Check yourself
An engineer wants to link 77 sensors so that each sensor is joined directly to exactly 33 others. Which statement is correct?

Turning a real situation into a graph

To model a situation, decide what the vertices are (places or objects) and what the edges are (direct links). Leave out real positions and the shapes of roads.

On a map, towns are vertices and roads are edges. In a circuit, junctions are vertices and each component between two junctions is an edge.

An unweighted graph only says whether two things are linked. A weighted graph is not drawn to scale, so read the weights, never the line lengths.

A graph with three vertices P, Q and R. Two separate edges join P and Q, one labelled battery and one labelled bulb. An edge labelled resistor joins P and R, and an edge labelled switch joins R and Q. battery bulb resistor switch P Q R
The circuit as a graph.
Worked exampleIn a circuit, a battery and a bulb are each connected directly between junctions P and Q. A resistor joins P to a junction R, and a switch joins R to Q. Model the circuit as a graph, and find the degrees of P, Q and R.

Try it first, then reveal one step at a time.

  1. Vertices: junctions P, Q and R. Edges: one per component, so 44 edges.
A weighted graph with vertices F, G, H and I. Edge weights: F to G 15, F to H 9, G to H 4, G to I 8, H to I 18, and F to I 24, drawn as a long curve over the top. 15 9 4 8 18 24 F G H I
Roads between four villages, in km. Not to scale.
Worked exampleThe roads between four villages are: Fenby–Garth 1515 km, Fenby–Holt 99 km, Garth–Holt 44 km, Garth–Ince 88 km, Holt–Ince 1818 km and a mountain road Fenby–Ince 2424 km. (a) Represent the roads as a weighted graph. (b) Find the shortest distance by road from Fenby to Ince.

Try it first, then reveal one step at a time.

  1. (a) One vertex per village and one edge per road, labelled with its length (see the figure).
Check yourself
On a weighted graph of roads, edge DS has weight 1212 km and is drawn shorter than edge DT, with weight 77 km. Which is correct?
Check yourself
A rail map shows 66 stations and the direct lines between them. You model it as a graph. What are the vertices?

Simple, complete and connected graphs

In KnK_n each vertex has degree n−1n - 1, so the degrees add to n(n−1)n(n - 1), and the number of edges is half of that.

Learn this
number of edges of Kn=n(n−1)2\text{number of edges of } K_n = \frac{n(n-1)}{2}

Every complete graph is connected. A connected graph need not be complete: some pairs may have no direct edge.

Three graphs. G1: a square A, B, C, D with edges AB, BC, CD, DA and a loop at C. G2: four vertices P, Q, R, S with all six edges, including the two diagonals, which cross without a vertex. G3: a triangle V, W, X and, separately, an edge joining Y and Z. G₁ G₂ G₃ A B C D P Q R S V W X Y Z
Three graphs to classify. In G2G_2 the diagonals cross, but there is no vertex where they cross.
Worked exampleFor each graph in the figure, state whether it is simple, connected and complete. Give a reason for each answer.

Try it first, then reveal one step at a time.

  1. G1G_1: the loop at C means not simple. The square reaches every vertex, so connected. A and C are not adjacent, so not complete.
Worked exampleIn a chess tournament, each player plays every other player exactly once. (a) Explain why the games can be modelled by a complete graph, and find the number of games for 1616 players. (b) The hall is booked for at most 100100 games. Use your calculator to find the largest number of players the tournament can take.

Try it first, then reveal one step at a time.

  1. (a) Players are vertices and games are edges. Every pair of players meets once, so the graph is K16K_{16}, with 16×152=120\frac{16 \times 15}{2} = 120 games.
Check yourself
A courier firm wants a direct flight route between every pair of its 1111 hubs. How many routes is that?
Check yourself
A graph has vertices A, B, C, D and edges AB, BC and CD only. Which description is correct?

Directed graphs

Some links work one way only, like one-way streets. Arrows on the edges record this.

A two-way link is drawn as two arrows, one each way.

In a directed graph with two or more vertices, a vertex with in-degree 00 can't be reached, and one with out-degree 00 is a dead end. Either means the graph is not strongly connected.

A directed graph with four vertices K, L, M and N. Arrows: K to L, L to M, M to K, L to N, and N to M. K L M N
One-way streets between four junctions.
Worked exampleThe figure shows one-way streets between junctions K, L, M and N. Find the in-degree and out-degree of each junction.

Try it first, then reveal one step at a time.

  1. The 55 edges are K→L, L→M, M→K, L→N and N→M.
Worked exampleFor the streets in the figure: (a) show that the network is strongly connected; (b) the council reverses the street from K to L, so it now runs from L to K. Determine whether the network is still strongly connected, and interpret your answer.

Try it first, then reveal one step at a time.

  1. (a) The route K→L→N→M→K follows the arrows and visits every junction. Going round it, any junction reaches any other.
Check yourself
A directed graph has 55 vertices and 99 edges. The out-degrees of four of the vertices are 2,1,02, 1, 0 and 33. Find the out-degree of the fifth vertex.
Check yourself
On a social app, an arrow from X to Y means X follows Y. Ana follows Ben and Cara, Ben follows Cara, and Cara follows Ana. Is the “follows” graph strongly connected?

Subgraphs and trees

You may keep a vertex without its edges, but not an edge without its ends, and you can't add new edges.

A graph G with six vertices A to F. Edges: A to B, A to C, B to C, B to D, C to E, D to E, D to F and E to F. A B C D E F
Graph GG, with 66 vertices and 88 edges.
Worked exampleFor the graph GG in the figure, decide which of these are subgraphs of GG. H1H_1: vertices A, B, C with edges AB and BC. H2H_2: vertices B, D, F with edges BD and BF. H3H_3: vertices D and E with edges DE and EF.

Try it first, then reveal one step at a time.

  1. H1H_1: AB and BC are edges of GG, with both ends kept. It is a subgraph.

A cycle is a closed route along edges back to its start, repeating no edge and no other vertex. A loop, or two edges between the same pair, is already a cycle. Cycles are studied in 3.16.

The reverse needs a condition: a graph with nn vertices and n−1n - 1 edges is a tree exactly when it is connected.

Trees model networks with no wasted link, such as water pipes. In 3.16 you find the cheapest tree joining every vertex.

Worked exampleA water company plans to link 99 farms with 88 pipes. The plan includes pipes PQ, QR and RP between farms P, Q and R. Explain why the plan is not a tree, and what this means for the farms.

Try it first, then reveal one step at a time.

  1. P–Q–R–P is a cycle, so the plan is not a tree.
Check yourself
A tree has 1212 edges. How many vertices does it have?
Check yourself
Each graph below has vertices A, B, C and D. Which one is a tree?

Common mistakes

  • Counting a loop once. Both ends of a loop are at the same vertex, so it adds 22 to that vertex's degree.
  • Calling a connected graph complete. Complete means every pair of vertices is joined directly; connected only needs a route between every pair.
  • Judging distances from the drawing. Weighted graphs are not to scale, and a route through other vertices can beat a direct edge.
  • Swapping in-degree and out-degree. In-degree counts arrows arriving at a vertex; out-degree counts arrows leaving it.
  • Calling a graph a tree from its edge count alone. A graph with nn vertices and n−1n - 1 edges is a tree only if it is also connected.
  • Drawing a graph with unlabelled vertices or needless crossings. Label every vertex and avoid crossing edges where you can.

Exam tips

  • “Write down the degree”: no working is needed, but count a loop twice and count every edge between the same two vertices.
  • “State, giving a reason” (simple, connected, complete): name the feature that decides it, such as a loop at C, or a pair of vertices with no edge between them.
  • “Explain why” a graph is connected but not complete: give both halves. Show a route that reaches every vertex, then name one pair of vertices that are not adjacent.
  • “Draw” a graph: one labelled vertex per place, one edge per direct link, weights on the edges if they are given, and arrows only for one-way links.

Key takeaways

Learn this∑deg⁡(V)=2×number of edges\sum \deg(V) = 2 \times \text{number of edges}
Learn thisDegree counts edge ends at a vertex: a loop adds 22, and each of several edges between the same two vertices counts.
Learn thisWeighted graph: each edge carries a distance, time or cost. The drawing is not to scale, so read the weights.
Learn thisSimple: no loops and no multiple edges. Complete KnK_n: simple, with every pair of its nn vertices joined, so it has n(n−1)2\frac{n(n-1)}{2} edges.
Learn thisConnected: you can travel along edges between any two vertices. Strongly connected (directed graph): you can travel from any vertex to any other following the arrows.
Learn thisIn a directed graph, the in-degrees add up to the number of edges, and so do the out-degrees.
Learn thisSubgraph: vertices and edges taken from GG, with both ends of every kept edge also kept.
Learn thisTree: connected with no cycles. A tree with nn vertices has n−1n - 1 edges, and a connected graph with nn vertices and n−1n - 1 edges is a tree.

Practise this

16 past-paper questions on Graph theory in the AI HL bank, each with a mark scheme and a worked explanation.

Practise Graph theory →