Graph theory basics
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 vertices has edges.
Before you start2 quick questions on what this builds on
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.
So the degrees always add to an even number.
Try it first, then reveal one step at a time.
- (a) B's edges go to A, C and D, so these are adjacent to B.
- (b) A: edges to B and C, so . B: edges to A, C and D, so .
- C: edges to A and B, plus two to D, so . D: edges to B and E, plus two to C, so .
- E: one edge to D, and the loop adds , so .
- Check: there are edges, and .
Try it first, then reveal one step at a time.
- Each switch is a vertex of degree , and each cable is an edge.
- The degrees add to , which is twice the number of edges.
- So there are cables. In context: counts every cable twice, once at each end.
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.
Try it first, then reveal one step at a time.
- Vertices: junctions P, Q and R. Edges: one per component, so edges.
- The battery and bulb both join P and Q: draw two edges between P and Q. The resistor gives PR and the switch gives RQ (see the figure).
- P meets the battery, bulb and resistor: . Q meets the battery, bulb and switch: . R: .
- Check: .
Try it first, then reveal one step at a time.
- (a) One vertex per village and one edge per road, labelled with its length (see the figure).
- (b) Routes from F to I: F–I , F–G–I , F–H–I , F–H–G–I , F–G–H–I .
- The shortest is km, via Holt and Garth. In context: the direct mountain road is km longer than going through two villages.
Simple, complete and connected graphs
In each vertex has degree , so the degrees add to , and the number of edges is half of that.
Every complete graph is connected. A connected graph need not be complete: some pairs may have no direct edge.
Try it first, then reveal one step at a time.
- : the loop at C means not simple. The square reaches every vertex, so connected. A and C are not adjacent, so not complete.
- : no loops or multiple edges, and all pairs of vertices are joined, so it is complete () and connected.
- : simple, but there is no route from V to Y, so not connected and not complete.
- : not simple (loop at C), connected, not complete. : simple, connected and complete (). : simple, not connected, not complete.
Try it first, then reveal one step at a time.
- (a) Players are vertices and games are edges. Every pair of players meets once, so the graph is , with games.
- (b) Write down the condition: .
- Table of : gives and gives .
- , so at most players. In context: a th player adds games, going over the limit.
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 can't be reached, and one with out-degree is a dead end. Either means the graph is not strongly connected.
Try it first, then reveal one step at a time.
- The edges are K→L, L→M, M→K, L→N and N→M.
- K: in from M, out to L. L: in from K, out to M and N. M: in from L and N, out to K. N: in from L, out to M.
- Check: in-degrees and out-degrees , the number of edges.
- K: in , out ; L: in , out ; M: in , out ; N: in , out .
Try it first, then reveal one step at a time.
- (a) The route K→L→N→M→K follows the arrows and visits every junction. Going round it, any junction reaches any other.
- (b) Now both of K's streets, L→K and M→K, arrive at K, so K has out-degree .
- No street leaves K, so the network is not strongly connected. In context: traffic at K would be trapped.
- (a) The route K→L→N→M→K visits every junction, so it is strongly connected. (b) K would have out-degree , so the network is not strongly connected: drivers at K could not leave.
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.
Try it first, then reveal one step at a time.
- : AB and BC are edges of , with both ends kept. It is a subgraph.
- : BF is not an edge of , so it is not a subgraph.
- : edge EF is kept but its end F is not, so it is not a subgraph.
- Only is a subgraph of .
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 vertices and 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.
Try it first, then reveal one step at a time.
- P–Q–R–P is a cycle, so the plan is not a tree.
- A connected graph with vertices and edges is a tree, with no cycle. This plan has a cycle, so it is not connected.
- In context: one triangle pipe is spare, and at least one farm is cut off.
- The triangle PQR is a cycle, so the plan is not a tree. With farms and pipes it is therefore not connected: at least one farm is cut off.
Common mistakes
- Counting a loop once. Both ends of a loop are at the same vertex, so it adds 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 vertices and 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
Practise this
16 past-paper questions on Graph theory in the AI HL bank, each with a mark scheme and a worked explanation.