Graph theory basics (simple/directed graphs, subgraphs, trees): notes and practice questions
- Vertex (Node): A point representing an object or place.
- Edge (Arc): A line connecting two vertices.
- Adjacent Vertices: Directly connected by an edge.
- Degree of a Vertex: Total number of edges connected to it.
- Loop: An edge starting and ending at the same vertex.
- Simple Graph: Undirected, unweighted, no loops, no multiple edges.
- Directed Graph (Digraph): Edges have a specific direction (arrows).
- In-degree: Number of edges leading into a vertex.
- Out-degree: Number of edges leaving from a vertex.
- Weighted Graph: Edges assigned numerical values (weights).
- Complete Graph: Every vertex is directly connected to every other vertex.
- Connected Graph: A route exists between any two vertices.
- Strongly Connected Graph (Digraph): A route exists in either direction between any two vertices, obeying arrow directions.
- Subgraph: A smaller graph containing a selection of edges and vertices from a main graph G.
- Tree: A connected graph with no cycles, where any two vertices are connected by exactly one path.
- Spanning Tree: A subgraph that is a tree and contains all vertices from the original graph G.
- Adjacency Matrix: A grid representing connections between vertices.
- Undirected Graph Matrix: Symmetrical along the leading diagonal. Diagonal entry is 0 for no loop, 2 for an undirected loop.
- Directed Graph Matrix: Not usually symmetrical. Diagonal entry is 1 for a directed loop.
- Walks of Length n: The number of walks of length from vertex A to vertex B is the value in row A, column B of the matrix .
- Walks of Length n or less: The total number of walks of length or less from vertex A to vertex B is the value in row A, column B of the sum:
- GDC Use: Use a Graphical Display Calculator (GDC) to compute matrix powers () and sums () for walks.
- Exam Technique: Clearly state the matrix calculation (e.g., ) used on the GDC for method marks.
How it is examined
Mostly vocabulary marks, one each, feeding into AHL 3.15 and AHL 3.16 where the real work is. Getting the terms exactly right matters: connected and strongly connected are different things, and a directed graph has in degree and out degree rather than a single degree. Questions usually supply the graph as a figure, so this subtopic needs figure support in the question rather than drawing support in the answer.
- Graph theory: graphs, vertices, edges, adjacent vertices, adjacent edges, and the degree of a vertex.
- Simple graphs, complete graphs, weighted graphs.
- Directed graphs; the in degree and out degree of a directed graph.
- Subgraphs; trees.
Linking questions
- Aim 8: the importance of symbolic maps, for example Metro and Underground maps, structural formulae in chemistry, electrical circuits.
- TOK: mathematics and knowledge claims. Consider the proof of the four-colour theorem. If a theorem is proved by computer, how can we claim to know it is true?
Practice questions
2 questions · 2 hardQuestion 1
HardPaper 1 · calculator5 marksA data network connects several hubs, represented by vertices A, B, C, D, E. The numbers on the edges represent the cost (in hundreds of dollars) to lay a new fibre optic cable between two hubs. An engineer needs to inspect all existing cables.
Write down the vertices with odd degree.
The total cost of all existing cables is dollars. The engineer wants to traverse every cable in the network, starting and ending at the same hub, while minimizing the total distance travelled. This may involve traversing some cables more than once.
Find two expressions, in terms of , for the minimum total cost (in hundreds of dollars) required to traverse all cables, beginning and ending at the same hub.
Include in your answer the interval of values of for which each expression is valid.
The degree of a vertex is the number of edges connected to it. A vertex has an odd degree if an odd number of edges connect to it.
To traverse all edges starting and ending at the same vertex, all vertices must have an even degree. Identify the odd-degree vertices from part (a). You need to add edges to the graph to make all degrees even. This involves finding the shortest paths between pairs of odd-degree vertices and choosing the pairing that minimizes the sum of these shortest paths. Consider different cases for the value of .
Question 2
HardPaper 3 · calculator14 marksA new suburb is being planned with 10 plots of land. The road network connecting these plots is modelled as a simple, connected graph , where the plots are vertices and roads are edges.
(a) (i) Write down the minimum number of roads required to connect all 10 plots.
(a) (ii) Find the maximum number of roads that could be built if every plot is directly connected to every other plot.
(a) (iii) The local council wants to design the road network so that a garbage truck can travel along each road exactly once and return to its starting depot (one of the plots). Find the maximum number of roads possible in such a network.
A biochemist is studying fullerenes, which are molecules of carbon in the form of a hollow sphere. The structure of a fullerene can be represented by a connected, planar graph , where carbon atoms are vertices (), covalent bonds are edges (), and the rings of atoms are faces (). Each face is a polygon with edges.
(b) (i) By considering the total number of edges counted face by face, explain why .
(b) (ii) A hypothetical fullerene, , is composed entirely of pentagonal faces (). Given that it has 20 vertices (), find the number of faces, .
(b) (iii) Another hypothetical fullerene has 28 vertices (). It is known that all its faces are identical polygons. Find the possible values for the number of faces, .
Think about the simplest type of connected graph. What is its name and how many edges does it have for a given number of vertices?
This describes a specific type of graph where every vertex is connected to every other vertex. What is the formula for the number of edges in such a graph?
For a garbage truck to travel each road exactly once and return, what condition must be met by the degree of each vertex? How does this limit the maximum number of edges?
Consider one face. It has 'm' edges. If you sum this over all 'f' faces, what do you get? Now consider a single edge. How many faces does it border?
You have two equations: Euler's formula for planar graphs and the formula from part (b)(i). You need to solve them simultaneously.
Use Euler's formula and the result from (b)(i) to create an equation relating 'f' and 'm'. Remember that both 'f' and 'm' must be integers, and a polygon must have at least 3 sides.
No question on this page matches those filters. Try another difficulty or paper.
Every Graph theory basics (simple/directed graphs, subgraphs, trees) question, marked for you
Every answer is marked mark by mark, IB-style, and the AI tutor helps when you are stuck.
Where marks are lost
- Answering to the wrong accuracy. Two significant figures, or six, where the rule says exactly or three. Common wherever a GDC's full decimal display gets copied straight down.
- Rounding an intermediate value and then using it in a later part. Costs a mark every time, and AI's multi-part modelling questions give it more chances to happen than AA's shorter, more self-contained ones.
- Writing the answer and nothing else, where the mark scheme has an explicit M1 rather than an implied one. A bare answer cannot score full marks there.
