Introduction to graph theory AI HL

IB Mathematics: Applications and Interpretation HL · Unit 3

Lesson 3.14 · Introduction to graph theory

Represent networks with vertices and edges, and interpret weighted, directed, and connected graphs.

Joined in praise

“O magnify the LORD with me, and let us exalt his name together.” Psalm 34:3 (KJV)

A network diagram helps us see connections between places or people. This psalm invites us to praise God together. As you study how individual vertices become part of a larger network, consider how you can encourage someone else and join them in giving thanks to the Lord.

Learning objectives

By the end of this lesson, you should be able to:

model a real network using vertices and edges;
identify adjacent vertices and adjacent edges, and calculate vertex degrees;
recognize simple, complete, weighted, and directed graphs;
interpret connectedness and strong connectedness;
find in-degrees and out-degrees in a directed graph; and
identify subgraphs and trees.

1. What is a graph?

In graph theory, a graph is a collection of vertices joined by edges. Vertices can represent stations, computers, towns, or people. Edges represent connections such as railway links, cables, roads, or relationships.

A graph records which objects are connected. The positions of its dots on the page need not match their geographical positions. Redrawing the same vertices and edges in a different arrangement does not change the graph.

The edge set is $\{AB,AC,BC,BD,CD,CE,DE\}$ . The drawing has five vertices and seven edges.

Worked example · Turn a description into a graph

A bus connects town $A$ to towns $B$ and $C$ . There is also a direct route between $B$ and $C$ . Represent the towns by vertices $A,B,C$ and the direct routes by edges $AB,AC,BC$ . The resulting graph is a triangle.

2. Adjacency and degree

Two vertices are adjacent if an edge joins them. Two edges are adjacent if they share a vertex. The degree of a vertex in an undirected graph is the number of edges incident to it.

In the diagram above, $B$ is adjacent to $A$ , $C$ , and $D$ , so $\deg(B)=3$ . The edges $AB$ and $BD$ are adjacent because they share $B$ . The edges $AB$ and $CE$ are not adjacent.

Every undirected edge contributes $1$ to the degree of each endpoint. Consequently, the sum of all vertex degrees equals twice the number of edges:

$\boxed{\text{Sum of degrees}=2\times\text{number of edges}}$

Worked example · Check a network

For the diagram above, the degrees of $A,B,C,D,E$ are $2,3,4,3,2$ . Their sum is $14$ , which equals $2(7)$ because the graph has seven edges.

3. Simple and complete graphs

A simple graph has no loops from a vertex back to itself and no repeated edges between the same pair of vertices. A complete graph joins every pair of distinct vertices. The complete graph on $n$ vertices is denoted by $K_n$ .

Each of the $n$ vertices in $K_n$ has degree $n-1$ . Counting all these degrees and dividing by two gives its number of edges:

$\boxed{\text{Edges in }K_n=\frac{n(n-1)}2}$

Worked example · Every pair connected

Six research stations each need a direct link to every other station. The network is $K_6$ and needs:

$\frac{6(6-1)}2=\boxed{15\text{ links}}$

Each station has degree $5$ .

4. Weighted graphs

A weighted graph assigns a number, called a weight, to each edge. A weight might represent distance, travel time, cost, or capacity. Specify what the weights mean and keep their units consistent.

Worked example · Compare two routes

Suppose direct road distances are $AB=4$ km, $AC=7$ km, and $BC=2$ km. The route from $A$ to $C$ through $B$ has total weight $4+2=6$ km. It is shorter than the direct edge $AC$ , whose weight is $7$ km.

Graph first, calculation second: A network may contain a short-looking line on the page with a large weight. Use the numerical edge weights when comparing routes.

5. Connected graphs and paths

A path is a sequence of joined vertices. An undirected graph is connected if a path exists between every pair of vertices. If some vertices cannot be reached from others, the graph is disconnected.

The five-vertex diagram above is connected: for example, $A\to C\to E$ is a path from $A$ to $E$ . A path need not use a direct edge between its endpoints.

Worked example · Loss of a connection

A network has vertices $A,B,C,D$ and edges $AB,BC,CD$ . It is connected. If edge $BC$ is removed, the graph separates into the groups $\{A,B\}$ and $\{C,D\}$ , so it is disconnected.

6. Directed graphs, in-degree, and out-degree

In a directed graph, an edge has an arrow. The edge $A\to B$ permits movement from $A$ to $B$ ; it does not automatically permit travel from $B$ to $A$ . Directed edges can also carry weights.

A vertex’s in-degree counts arrows arriving at it. Its out-degree counts arrows leaving it. Every arrow has one start and one end, so:

$\boxed{\text{Sum of in-degrees} =\text{Sum of out-degrees} =\text{number of directed edges}}$

A directed graph is strongly connected if, for every pair of vertices, one can travel from the first to the second following the arrows.

Worked example · One-way streets

A one-way network has edges $A\to B$ , $B\to C$ , $C\to A$ , and $C\to D$ . Vertex $C$ has in-degree $1$ and out-degree $2$ . The whole graph is not strongly connected because there is no directed route from $D$ back to $A$ , $B$ , or $C$ .

7. Subgraphs and trees

A subgraph uses some vertices and some edges of a larger graph, retaining only edges whose endpoints are included. A tree is a connected graph with no cycles. A cycle is a closed route that returns to its starting vertex without repeating other vertices.

A tree on $n$ vertices has exactly $n-1$ edges. There is exactly one path between any two vertices of a tree.

Worked example · Select a tree

Take the five-vertex graph in Section 1. Keep all its vertices but only edges $AB$ , $BC$ , $CD$ , and $DE$ . This subgraph is connected, has no cycle, and has $5-1=4$ edges. Therefore it is a tree.

Looking ahead: A spanning tree includes every vertex of a connected graph. If the graph is weighted, a minimum spanning tree is a spanning tree with the least possible total edge weight; finding one is a later network-optimization skill.

IB-style Paper 1 · Skill practice

A graph has vertices $A,B,C,D$ and edges $AB,AC,BC,CD$ . Find the degree of each vertex and check the sum-of-degrees rule. [4 marks]

Show solution

$\deg(A)=2$ , $\deg(B)=2$ , $\deg(C)=3$ , and $\deg(D)=1$ . Their sum is $8=2(4)$ , matching the four edges.
How many edges does $K_8$ have? What is the degree of each vertex? [3 marks]

Show solution

$\text{Edges}=\frac{8(7)}2=\boxed{28}$

Each vertex has degree $\boxed{7}$ .
A directed graph has edges $A\to B$ , $A\to C$ , $B\to C$ , $C\to A$ , and $C\to D$ . Find the in-degree and out-degree of $C$ . [3 marks]

Show solution

Arrows from $A$ and $B$ arrive at $C$ , so its in-degree is $\boxed{2}$ . Arrows from $C$ go to $A$ and $D$ , so its out-degree is $\boxed{2}$ .
A connected graph has $9$ vertices and $8$ edges. Can you conclude that it is a tree? Explain. [3 marks]

Show solution

Yes. A connected graph with $n$ vertices and $n-1$ edges has no cycles and is a tree. Here $8=9-1$ .
In a weighted network, edges $AB$ , $BC$ , and $AC$ have weights $7$ , $4$ , and $13$ , respectively. Compare the two routes from $A$ to $C$ . [3 marks]

Show solution

The route $A\to B\to C$ has weight $7+4=\boxed{11}$ ; the direct edge has weight $13$ . The route through $B$ is shorter by $2$ weight units.
A graph has vertices $A,B,C,D,E$ and edges $AB,BC,CA,CD,DE$ . Is it connected? Is it a tree? [4 marks]

Show solution

It is connected: each vertex can be reached from every other. It is not a tree because $A\to B\to C\to A$ is a cycle.

IB-style applications · Linked questions

The following questions use one network across several connected parts. Each solution explains the graph decision as well as the calculation.

Application 1 · Regional transport network

Five towns $A,B,C,D,E$ are joined by undirected roads. Their direct road connections are:

$AB,\ AC,\ BC,\ BD,\ CD,\ CE,\ DE$

State the order and size of the graph. [2 marks]
Find the degree of each vertex and verify the sum-of-degrees rule. [5 marks]
State whether the graph is connected. Give a path from $A$ to $E$ as evidence. [3 marks]

Show worked solution · Application 1

(a) The graph has $\boxed{5}$ vertices (order) and $\boxed{7}$ edges (size).

(b) The degrees of $A,B,C,D,E$ are $\boxed{2,3,4,3,2}$ , respectively. Their sum is $2+3+4+3+2=14=2(7)$ .

(c) Yes, it is connected. For example, $A\to C\to E$ is a path from $A$ to $E$ , and all remaining vertices join the same network.

Application 2 · Weighted delivery routes

A delivery network has undirected edges with the following distances in kilometres:

$AB=4$ , $AC=7$ , $BC=2$ , $BD=5$ , $CD=1$ , $CE=6$ , $DE=3$ , $DF=8$ , and $EF=2$ .

Calculate the total length of the routes $A\to C\to E\to F$ and $A\to B\to C\to D\to E\to F$ . [4 marks]
Find a shortest route from $A$ to $F$ and state its length. Show why going directly from $D$ to $F$ is less effective once $D$ has been reached. [5 marks]
A van must use roads with a total length below $13$ km. Determine whether it can travel from $A$ to $F$ under this limit. [2 marks]

Show worked solution · Application 2

(a) The first route has length $7+6+2=\boxed{15\text{ km}}$ . The second has length $4+2+1+3+2=\boxed{12\text{ km}}$ .

(b) A shortest route is $\boxed{A\to B\to C\to D\to E\to F}$ , of length $\boxed{12\text{ km}}$ . From $D$ , using $D\to E\to F$ costs $3+2=5$ km, less than the direct edge $DF=8$ km. To reach $D$ from $A$ , $A\to B\to C\to D$ costs $4+2+1=7$ km; alternatives $A\to C\to D$ and $A\to B\to D$ cost $8$ and $9$ km. Thus the displayed route achieves the shortest total.

(c) Yes. $\boxed{12<13}$ , so the van meets the limit.

Application 3 · One-way shuttle service

Four campuses $A,B,C,D$ are connected by one-way shuttle routes:

$A\to B,\quad B\to C,\quad C\to A,\quad C\to D,\quad D\to B$

State the in-degree and out-degree of each campus. [4 marks]
Determine whether the directed graph is strongly connected. Give a directed route from $D$ to $A$ and one from $A$ to $D$ . [4 marks]
If the route $D\to B$ is closed, determine whether the remaining directed graph is strongly connected. [2 marks]

Show worked solution · Application 3

(a) In-degree and out-degree, respectively: $A:(1,1)$ , $B:(2,1)$ , $C:(1,2)$ , $D:(1,1)$ . Both degree totals equal $5$ , the number of arrows.

(b) Yes. Routes include $D\to B\to C\to A$ and $A\to B\to C\to D$ . The cycle $A\to B\to C\to A$ , together with routes into and out of $D$ , makes every vertex reachable from every other.

(c) No. Without $D\to B$ , there is no route leaving $D$ , so a traveller at $D$ cannot reach another campus.

Application 4 · Planning a fibre-optic network

Five offices $A,B,C,D,E$ can be linked by cables. The available undirected links have costs, in thousands of euros: $AB=4$ , $AC=7$ , $BC=2$ , $BD=5$ , $CD=1$ , $CE=6$ , and $DE=3$ .

Explain why links $AB$ , $BC$ , $CD$ , and $DE$ form a tree connecting all five offices. [3 marks]
Find the total cost of these four links. [2 marks]
An engineer proposes adding $CE$ . Explain what happens to the tree property, and find the resulting total cost. [3 marks]

Show worked solution · Application 4

(a) These edges form the chain $A-B-C-D-E$ . It connects every office, has no cycle, and uses $5-1=4$ edges, so it is a tree.

(b) Cost $=4+2+1+3=\boxed{10}$ thousand euros.

(c) Adding $CE$ creates the cycle $C\to D\to E\to C$ . The graph is no longer a tree. Its total cost becomes $10+6=\boxed{16}$ thousand euros.

Application 5 · Completing a communication network

Seven research centres each require a direct two-way communication link to every other centre. At present, the network contains $14$ different direct links. There are no loops or repeated links.

Find the number of links needed for the complete network. [3 marks]
Find how many additional links must be installed. [2 marks]
One centre currently has degree $5$ . Explain how many new links involving that centre it requires. [2 marks]

Show worked solution · Application 5

(a) A complete graph on seven vertices has $\frac{7(6)}2=\boxed{21}$ links.

(b) The network needs $21-14=\boxed{7}$ additional links.

(c) Every vertex of $K_7$ has degree $6$ . A centre of degree $5$ therefore needs $\boxed{1}$ additional link incident to it. The seven links in part (b) are for the whole network, not seven links for each centre.

Reflection · Connections that encourage

Graph theory shows how separate points become part of a connected network. Psalm 34:3 invites us to praise the Lord together. Who could you encourage or pray with this week so that neither of you walks alone?

Lesson 3.14 · Introduction to graph theory

Joined in praise

Learning objectives

1. What is a graph?

2. Adjacency and degree

3. Simple and complete graphs

4. Weighted graphs

5. Connected graphs and paths

6. Directed graphs, in-degree, and out-degree

7. Subgraphs and trees

IB-style Paper 1 · Skill practice

IB-style applications · Linked questions

Application 1 · Regional transport network

Application 2 · Weighted delivery routes

Application 3 · One-way shuttle service

Application 4 · Planning a fibre-optic network

Application 5 · Completing a communication network

Reflection · Connections that encourage

Related

Company

Links

Support

Recommend

alphy school publishers

IB Mathematics: Applications and Interpretation HL 6 Sections80 LessonsLifetime

Curriculum

Introduction to graph theory AI HL

Lesson 3.14 · Introduction to graph theory

Joined in praise

Learning objectives

1. What is a graph?

2. Adjacency and degree

3. Simple and complete graphs

4. Weighted graphs

5. Connected graphs and paths

6. Directed graphs, in-degree, and out-degree

7. Subgraphs and trees

IB-style Paper 1 · Skill practice

IB-style applications · Linked questions

Application 1 · Regional transport network

Application 2 · Weighted delivery routes

Application 3 · One-way shuttle service

Application 4 · Planning a fibre-optic network

Application 5 · Completing a communication network

Reflection · Connections that encourage

Related

Leave A Reply Cancel reply

Company

Links

Support

Recommend

alphy school publishers

Customise Consent Preferences

Log in with your account

Modal title