HL · Graphs & algorithms 1 · Graphs, vertices & degree

Module 24 of 47Lesson 1 of 8 · HL · Graphs & algorithms 1 · Graphs, vertices & degree

Graphs & algorithms · Essential understanding 1

Graphs, vertices & degree

IB AI AHL 3.14with Prof. Kitso

💻 Using the TI-Nspire CX Student Software on a laptop

The screens in these notes are drawn exactly as the Student Software shows them. The keypad on the left of the software works like the handheld — click its keys with the mouse.
menu: click menu on the on-screen keypad (or Documents Toolbox ▸ 🔧). The menu numbers and letters are the same as in these notes.
enter = Enter · tab = Tab (next box) · esc = Esc · del = Backspace.
Powers: type ^ (Shift+6), the power, then press → to come back down before typing more. x² = ^2 then →.
Fraction: type / · √: type sqrt( · π: type pi · eˣ: type exp( · store: type :=. For EE (×10ⁿ) and i, click them on the keypad.
New page: Ctrl+I (or the Insert menu) · change page: Ctrl+← / Ctrl+→ · graph entry line: Ctrl+G · var: Ctrl+L.
Radian / Degree: click Settings in the status bar at the bottom of the window. The mode (RAD or DEG) shows in the top bar.
IB exam mode (Press-to-Test): everything in these notes works on the non-CAS TI-Nspire with the IB exam settings. In exam mode there are no dot-product, cross-product, unit-vector or eigenvalue keys and no Diff Eq graphs — the notes show the allowed way (type the components, use polyRoots on the characteristic equation, do Euler steps on a Calculator page).
If you type nDeriv(, the software shows it as centralDiff( — it is the same command.

The big idea: A graph is a picture of connections: dots called vertices joined by lines called edges. The degree of a vertex is how many edges meet there, and the degrees of any graph always add up to twice the number of edges.

By the end of this lesson you can:

name the parts of a graph: vertices, edges, adjacent vertices, degree, loops and multiple edges
recognise a simple, complete, connected and weighted graph, a subgraph and a tree
use sum of degrees = 2 × number of edges and the edge count of a complete graph
work with directed graphs: in-degree, out-degree and strongly connected
turn a real situation (roads, flights, matches) into a graph

🧑🏾 Imagine this…

Look at a bus map of Botswana. You do not care how bendy the road from Gaborone to Francistown is, or where the trees are. You only care which towns are joined. Rub out everything else and you are left with dots (towns) and lines (roads). That stripped-down picture is a graph. Graph theory is the maths of such pictures, and it powers satnav routes, delivery planning and even internet search.

Graph

a set of vertices (dots, also called nodes) joined by edges (lines). Only the connections matter, not how you draw them.

Adjacent

two vertices are adjacent if an edge joins them directly. In the graph below, A and B are adjacent but B and F are not.

Degree of a vertex

the number of edges that meet at the vertex. A loop (an edge from a vertex to itself) counts twice.

Simple graph

no loops and no two edges joining the same pair of vertices.

Complete graph

K_n

a simple graph on

n

vertices where every pair of vertices is joined by an edge.

Connected graph

you can get from any vertex to any other by following edges. If not, the graph is in separate pieces.

Subgraph

a graph made from some of the vertices and some of the edges of a bigger graph.

Tree

a connected graph with no cycles (no closed loop of edges that returns to its start without repeating a vertex).

Weighted graph

each edge carries a number (the weight): a distance, a cost or a time.

Directed graph (digraph)

each edge has a direction (an arrow), such as a one-way street. Out-degree = arrows leaving a vertex, in-degree = arrows arriving.

Strongly connected

a directed graph where you can get from any vertex to any other by following the arrows.

A simple connected graph with 6 vertices and 7 edges. The degree of each vertex is written beside it. The degrees add up to 3 + 2 + 3 + 2 + 3 + 1 = 14, which is 2 × 7.

Four kinds of graph. The complete graph K4 has every pair joined. The tree is connected with no cycle. The third graph has a double edge and a loop, so it is not simple. The last graph is directed: each edge is an arrow.

★ Facts you must know

Handshaking lemma: the sum of all the degrees $= 2 \times$ (number of edges). Every edge has two ends, so it is counted twice.
So the sum of degrees is always even, and the number of vertices with odd degree is always even.
Complete graph: $K_n$ has $\dfrac{n(n-1)}{2}$ edges, and every vertex has degree $n-1$ .
Tree: a tree with $n$ vertices has exactly $n-1$ edges.
Directed graph: (sum of in-degrees) $=$ (sum of out-degrees) $=$ number of edges.

⚠️ Watch out

A graph is not a function graph. There are no axes. Two drawings that look different can be the same graph if the same vertices are joined.
A loop adds 2 to the degree, not 1.
Connected and complete are different words. A path A–B–C is connected but not complete (A and C are not joined).
In a directed graph, strongly connected needs a route in both directions between every pair, following the arrows.

🧪 Try it yourselfTree or not a tree?

A tree is connected with no cycle, and with

n

vertices it has exactly

n-1

edges. Count the vertices and edges, then decide.

Worked examples

Example 1.1Degrees and the handshaking lemma

The graph shows six villages A–F and seven roads.

(a) Write down the degree of each vertex.
(b) Show that the sum of the degrees equals twice the number of edges.
(c) List the vertices of odd degree and the vertices adjacent to E.

🧠 Think it through

Degree = how many edges touch the vertex. Go vertex by vertex and count the lines.
Add all six degrees. Then count the edges on the picture and double it.
Odd degree means 1, 3, 5 … Adjacent to E means joined directly to E.

✍️ By hand

A: AB, AC, AD

\to 3

. B: AB, BC

\to 2

. C: AC, BC, CE

\to 3

. D: AD, DE

\to 2

. E: CE, DE, EF

\to 3

. F: EF

\to 1

Sum

= 3 + 2 + 3 + 2 + 3 + 1 = 14

and

2 \times 7 = 14

✓

✅ Answer (a) A 3, B 2, C 3, D 2, E 3, F 1. (b) The degrees add to 14 and there are 7 edges, so 14 = 2 × 7. (c) Odd degree: A, C, E, F (four of them, an even number, as it must be). Adjacent to E: C, D and F.

Command term show that: write both sides of the equation and finish with “so they are equal”.

Example 1.2Is this graph possible?

Decide, with a reason, whether each simple graph can exist, and answer the last two parts.

(a) A graph with six vertices of degrees 3, 3, 2, 2, 2, 1.
(b) A graph with 7 vertices, each of degree 4: how many edges does it have?
(c) A complete graph has 45 edges. How many vertices does it have?
(d) What is the degree of every vertex of that complete graph?

🧠 Think it through

Add the degrees. The total must be even, because it equals 2 × edges.
Edges $= \dfrac{\text{sum of degrees}}{2}$ .
A complete graph $K_n$ has $\dfrac{n(n-1)}{2}$ edges. Set that equal to 45 and solve for $n$ .

✍️ By hand

(a)

3+3+2+2+2+1 = 13

, which is odd.

(b)

7 \times 4 = 28

, so edges

= \dfrac{28}{2} = 14

(c)

\dfrac{n(n-1)}{2} = 45 \Rightarrow n^2 - n - 90 = 0 \Rightarrow (n-10)(n+9) = 0 \Rightarrow n = 10

(a vertex count cannot be negative).

🔢 On your TI-Nspire CX II

For (c) you can also solve with the calculator. Type nSolve(n*(n-1)/2=45,n=8) and press enter ↵💻 Enter. The guess n = 8 steers it to the positive answer.
📍 Where to find it on the TI-Nspire
nSolve( is in menu💻 click menu on keypad▸3: Algebra▸1: Numerical Solve

✅ Answer (a) Impossible: the degrees add to 13, which is odd, but the sum of degrees must be even. (b) 14 edges. (c) 10 vertices. (d) Each vertex has degree 9.

Never leave a quadratic answer as “n = 10 or n = −9”. A number of vertices must be a positive whole number, so say which root you reject and why.

Example 1.3Naming a graph and its parts

Graph H has five vertices P, Q, R, S, T. There is one edge each for PQ, RS, SP and ST, and two edges between Q and R.

(a) Is H simple? Is it connected? Is it complete?
(b) Find the degree of each vertex and check the handshaking lemma.
(c) Draw a subgraph of H that is a tree containing all five vertices.

🧠 Think it through

Simple means no loop and no repeated edge. Look for the double edge.
Connected: can you get from every vertex to every other? Complete needs every pair joined (10 pairs for 5 vertices).
A tree on 5 vertices needs 4 edges and no cycle. Keep the graph connected but break every cycle.

✍️ By hand

P: PQ, SP

\to 2

. Q: PQ and two QR

\to 3

. R: two QR and RS

\to 3

. S: RS, SP, ST

\to 3

. T: ST

\to 1

Sum

= 2 + 3 + 3 + 3 + 1 = 12 = 2 \times 6

✓ (there are 6 edges).

Tree: keep PQ, QR (just one of the two), RS and ST. This path P–Q–R–S–T has 4 edges and no cycle.

✅ Answer (a) Not simple (double edge QR). Connected: yes. Complete: no (for example P and R are not joined, and a simple complete graph on 5 vertices needs 10 edges). (b) P 2, Q 3, R 3, S 3, T 1; the sum is 12 = 2 × 6 edges. (c) A path such as PQ, QR, RS, ST is a spanning tree (a subgraph with 5 vertices, 4 edges, no cycle).

A tree that contains all the vertices of the graph is called a spanning tree. Lesson 5 is all about finding the cheapest one.

Example 1.4Directed graphs: in-degree, out-degree

The directed graph shows one-way bus routes between four stops A, B, C, D: A→B, B→C, C→A, C→D and D→B.

(a) Make a table of the in-degree and out-degree of each vertex and check the totals.
(b) Show that the graph is strongly connected.
(c) The route D→B is cancelled. Explain why the graph is no longer strongly connected, and suggest one new route that makes it strongly connected again.

🧠 Think it through

Out-degree: arrows leaving. In-degree: arrows arriving. Both totals must equal the number of edges, 5.
Find a route that follows the arrows and visits every stop, then back to the start. If one exists, every stop can reach every other.
Without D→B, what leaves D? Nothing. Once you reach D you are stuck.

✍️ By hand

\begin{array}{c|cccc} & A & B & C & D \\ \hline \text{out} & 1 & 1 & 2 & 1 \\ \text{in} & 1 & 2 & 1 & 1 \end{array}

Both rows add to 5 ✓

Closed route: A→B→C→D→B→C→A. It visits all four stops and returns to A, so each stop can reach each other stop.

✅ Answer (a) Out-degrees A1, B1, C2, D1 (total 5); in-degrees A1, B2, C1, D1 (total 5). (b) The route A→B→C→D→B→C→A passes through every vertex and returns to A, so the graph is strongly connected. (c) D then has out-degree 0: you can reach D but never leave it. Adding a route D→A (or D→B again, or D→C) means D can be left again, and every stop can again reach every other.

To disprove strong connectivity you only need one pair of vertices with no route between them (here C to D works, but D to anything fails).

Example 1.5Modelling a league as a graph

Six school netball teams form a league. Draw each team as a vertex and join two teams by an edge if they play each other.

(a) In a round robin every team plays every other team once. How many matches are played? What is each team's degree?
(b) Instead, each team plays exactly 3 matches. How many matches are there in total?
(c) Could 5 teams each play exactly 3 matches? Explain.

🧠 Think it through

A round robin on 6 teams is the complete graph $K_6$ .
If every vertex has degree 3, the degree sum is the number of teams × 3. Then halve.
Check that the degree sum would be even.

✍️ By hand

(a)

K_6

: edges

= \dfrac{6 \times 5}{2} = 15

. Each team plays the other 5.

(b) Sum of degrees

= 6 \times 3 = 18

, so matches

= \dfrac{18}{2} = 9

(c)

5 \times 3 = 15

is odd, but a degree sum must be even.

✅ Answer (a) 15 matches, every team has degree 5. (b) 9 matches. (c) No: 5 teams × 3 matches = 15 is odd, so the degrees could never add to 2 × (number of matches).

“Show that it is impossible” questions almost always use the handshaking lemma: find the degree sum and show it is odd.

Challenge questions

⭐ Challenge 1.6A missing degreePaper 1 style

A simple connected graph has five vertices with degrees 4, 3, 3,

x

, 1 and has exactly 7 edges.

(a) Find $x$ .
(b) Explain why the vertex of degree 4 must be adjacent to every other vertex.
(c) State, with a reason, whether the graph is a tree.

✏️ Try it on paper and on your calculator first. Then check.

Show the full solution

🧠 Think it through

Sum of degrees = 2 × 7.
Degree 4 with only 4 other vertices means every other vertex is a neighbour.
A tree on 5 vertices has how many edges?

✍️ By hand

4 + 3 + 3 + x + 1 = 14 \Rightarrow 11 + x = 14 \Rightarrow x = 3

✅ Answer (a)

x = 3

. (b) The graph is simple, so a vertex has at most one edge to each of the 4 other vertices. Degree 4 therefore uses one edge to each of them. (c) Not a tree: a tree with 5 vertices has 4 edges but this graph has 7 (so it contains cycles).

⭐ Challenge 1.7Ferries on the OkavangoPaper 2 style

Five landing stations P, Q, R, S, T on the Okavango are linked by one-way ferry routes: P→Q, P→R, Q→S, R→Q, R→S, S→T and T→P.

(a) Complete a table of in-degree and out-degree for each station and show that each row adds to the number of routes.
(b) Which stations have the greatest in-degree?
(c) Show that the network is strongly connected.
(d) The route T→P is withdrawn. Explain why the network is no longer strongly connected.
(e) Write down the only single new one-way route that restores strong connectivity, and justify your answer.

✏️ Try it on paper and on your calculator first. Then check.

Show the full solution

🧠 Think it through

Count arrows out of and into each vertex. There are 7 routes.
For (c) find a closed route through all five stations that follows the arrows.
After T→P goes, look at what leaves T and what arrives at P.
A fix must give T a way out and give P a way in.

✍️ By hand

\begin{array}{c|ccccc} & P & Q & R & S & T \\ \hline \text{out} & 2 & 1 & 2 & 1 & 1 \\ \text{in} & 1 & 2 & 1 & 2 & 1 \end{array}

Each row adds to 7.

Closed route: P→R→Q→S→T→P visits all five stations.

✅ Answer (a) Out: P2, Q1, R2, S1, T1 (sum 7). In: P1, Q2, R1, S2, T1 (sum 7). (b) Q and S, in-degree 2. (c) P→R→Q→S→T→P goes through every station and returns, so every station can reach every other. (d) T→P was the only route leaving T and the only route entering P, so after it is withdrawn nobody can leave T and nobody can reach P. (e) The route T→P itself: any new route must give T an exit and give P an entrance, and only an arrow from T to P does both.

Next: Lesson 2 · Walks, trails, Euler & Hamilton

IB DP Mathematics: Applications and Interpretation (AI) — SL and HL HL · Graphs & algorithms 1 · Graphs, vertices & degree

IB DP Mathematics: Applications and Interpretation (AI) — SL and HL

Graphs, vertices & degree

Worked examples

Challenge questions