Speak Maths · University

Graphs: dots, lines and counting walks

A graph is dots joined by lines: the simplest picture of anything connected, from paths in a park to friendships to the internet. A small table of 0s and 1s can hold the whole picture.

Draft: written by an AI helper and not yet checked by a teacher.

The alphabet

Read each sign aloud, the way it is written under it.

$G = (V, E), ∣ V ∣, ∣ E ∣$ Say: G equals V and E; the size of V, the size of EMeans: A graph G is a set V of vertices (dots) and a set E of edges (lines); bars count how many.
$de g v$ Say: the degree of vMeans: How many edges touch the vertex v.
$u \sim v$ Say: u is adjacent to v (u tilde v)Means: u and v are joined by an edge: they are neighbours.
$v_{0} \sim v_{1} \sim \dots \sim v_{k}, v_{k} = v_{0}$ Say: v zero is adjacent to v one, and so on to v k; if v k is v zero again, it is a cycleMeans: A path moves along edges from one vertex to another; ending where it began makes a cycle.
$∣ E ∣ = ∣ V ∣ - 1$ Say: the number of edges is the number of vertices minus oneMeans: A connected graph with this count is a tree: joined, with no cycle.
$A_{uv} = 1 \Leftrightarrow u \sim v$ Say: A of u, v is one exactly when u is adjacent to vMeans: The adjacency matrix A has a 1 where there is an edge and a 0 where there is none.
$(A^{2})_{ij} = \sum_{k} A_{ik} A_{k j}$ Say: A squared, entry i j, is the sum over k of A i k times A k jMeans: This entry counts the walks of length two from i to j: one for each middle vertex k.
$\sum_{v \in V} de g v = 2 ∣ E ∣$ Say: the sum of deg v over all v in V equals two times the number of edgesMeans: Every edge has two ends, so adding all the degrees counts each edge twice.

The story: The bridges of a park

Subtitles:

Tap a line to see its words.

$G = (V, E)$ A park has some spots and the paths between them. Draw a dot for each spot and a line for each path: a graph.
$∣ V ∣ = 5, ∣ E ∣ = 5$ The park has five spots, called a to e, and five paths.
$b \sim c, b \sim d, a ≁ d$ Spot b is next to c and to d; spot a is not next to d.
$de g b = 3, de g a = 1$ Three paths meet at b; only one reaches a.
$a \sim b \sim d \sim e$ A walk from a to e that never repeats a spot: a path of three steps.
$b \sim c \sim d \sim b$ From b to c to d and back to b: a cycle, a round trip.
$v \in V \sum de g v = 1 + 3 + 2 + 3 + 1 = 10 = 2 \cdot 5$ Add up the paths meeting at each spot: ten, which is twice the five paths, since each path has two ends.
$A_{b c} = 1, A_{a d} = 0$ In the table of 0s and 1s, the entry for b and c is 1; for a and d it is 0.
$(A^{2})_{a d} = 1$ Multiplying the table by itself shows one walk of two steps from a to d: through b.
$∣ E ∣ = 4 = ∣ V ∣ - 1$ The council closes the path between c and d. Now the park has one path fewer than spots: a tree.

In words this story is 749 letters long; in symbols, 104.

Read it

What does it say?

$u \sim v$

$de g v = 0$

$∣ E ∣ = ∣ V ∣ - 1$

$(A^{2})_{ij} = 3$

$∣ V ∣ = 6, ∣ E ∣ = 9$

$de g v = ∣ V ∣ - 1$

$a ≁ b$

$A_{v v} = 0$

$v \in V \sum de g v = 14$

$v_{0} \sim v_{1} \sim v_{2} \sim v_{3}$

$(A^{2})_{ii} = de g i$

$∣ E ∣ = ∣ V ∣$

Write it

Which notation says this?

The degree of the vertex v is four.

Adding up all the degrees gives twice the number of edges.

The number of walks of length two from i to j is the entry in row i, column j of the matrix A squared.

The vertices a and b are not adjacent.

A walk of two steps: from a to b, then from b to c.

A cycle of length three: a to b to c and back to a.

The graph has seven vertices and six edges.

A graph with ten edges: its degrees add up to twenty.

The vertex v is isolated: no edge touches it.

In the adjacency matrix: there is no edge between u and v.

The number of walks of length three from i to j.

A tree with n vertices has n minus one edges.

Build it

Tap the tiles in order. One tile does not belong.

The number of edges is the number of vertices, minus one.

The entry of A at u and v is one exactly when u and v are adjacent.

The number of two-step walks from i to j: the sum over k of A at i, k times A at k, j.

A cycle of four vertices: a to b, to c, to d, and back to a.

The degree of v is the sum of row v of the adjacency matrix.

In a tree the degrees add up to twice the number of edges, and the edges are the vertices minus one.

Challenges

Creative puzzles that use every sign of this chapter. Take your time; there is no clock.

1 The park, as a table

The table is the adjacency matrix of the park from the story. Judge each sentence about the park.

	$a$	$b$	$c$	$d$	$e$
$a$		✓
$b$	✓		✓	✓
$c$		✓		✓
$d$		✓	✓		✓
$e$				✓

A tick means the spot in the row is adjacent to the spot in the column.

$de g b = 3$
$\forall v : de g v \geq 1$
$\exists v : de g v = 0$
$a \sim e$
$\exists u \exists v : u \sim v \land de g u = de g v = 3$
$\exists v \forall u \neq = v : u \sim v$

2 Graph words

Five lines about a graph. Pair each with what it says.

Tap a line, then its meaning.

3 A tree’s count

A tree on the park’s spots must have one path fewer than spots. One tile is wrong. Find it, then fix it.

Tap the tile that is wrong.

4 Two ends to every path

This should say that the degrees add up to twice the number of edges. One tile is wrong. Find it, then fix it.

Tap the tile that is wrong.

5 Walks of two steps

The matrix is the 4-cycle: four spots in a ring, each next to its two neighbours. How many walks of two steps lead from vertex 1 to vertex 3?

$A = 0101101001011010, (A^{2})_{13} = ?$

6 An impossible set of degrees

Five spots have degrees 3, 3, 2, 2 and one more, x. Which value of x is impossible?

$de g = (3, 3, 2, 2, x)$

7 A busy but not too busy park

Every spot touches at least one path, but no spot touches all the other spots. Write it in symbols.

Your version

8 A friend in common

Any two different spots have a spot adjacent to both. Write it in symbols.

Your version

9 The hub

Five rooms of a house and the doors between them, as an adjacency matrix. Judge each sentence about this graph.

	$p$	$q$	$r$	$s$	$t$
$p$		✓	✓	✓	✓
$q$	✓		✓
$r$	✓	✓
$s$	✓
$t$	✓

A tick means the room in the row has a door to the room in the column.

$\exists v \forall u \neq = v : u \sim v$
$\sum_{v \in V} de g v = 10$
$∣ E ∣ = ∣ V ∣ - 1$
$q \sim r \sim p \sim q$
$s \sim t$
$(A^{2})_{s t} = 1$

10 Six stations, five tracks

Six stations on a small railway and the tracks between them, as an adjacency matrix. Judge each sentence about this graph.

	$a$	$b$	$c$	$d$	$e$	$f$
$a$		✓
$b$	✓		✓
$c$		✓		✓	✓
$d$			✓
$e$			✓			✓
$f$					✓

A tick means a track joins the station in the row to the station in the column.

$∣ E ∣ = ∣ V ∣ - 1$
$\exists v : de g v = 3$
$\forall v : de g v \leq 2$
$a \sim b \sim c \sim e \sim f$
$\exists u, v, w : u \sim v \sim w \sim u$
$\sum_{v \in V} de g v = 12$

11 Reading the table

Five things one can read off an adjacency matrix. Pair each with its meaning.

Tap a line, then its meaning.

12 Five counts

Five counts about a graph. Pair each with what it counts.

Tap a line, then its meaning.

13 Through the middle

This should count the two-step walks from i to j: a step from i to some k, then a step from k to j. One tile is wrong. Find it, then fix it.

Tap the tile that is wrong.

14 Close the loop

This should be a cycle through a, b and c: three steps that return to the start. One tile is wrong. Find it, then fix it.

Tap the tile that is wrong.

15 Six spots, two paths each

Six spots in a park, each with exactly two paths. How many paths are there?

$de g = (2, 2, 2, 2, 2, 2), ∣ E ∣ = ?$

16 A tree of ten

A tree has ten vertices. What do its degrees add up to?

$∣ V ∣ = 10, ∣ E ∣ = ∣ V ∣ - 1, v \in V \sum de g v = ?$

17 Out and back

Four spots, every pair joined by a path. How many walks of two steps start at spot 1 and end at spot 1?

$A = 0111101111011110, (A^{2})_{11} = ?$

18 Three paths from everywhere

In this park every spot has exactly three paths. Write it in symbols, then compare.

Your version

19 A triangle somewhere

Somewhere in the graph three vertices are each adjacent to the other two. Write it in symbols, then compare.

Your version

Tell your own

Draw a small graph of your own (a road map, a family, a game board) and write its vertices, its edges, and the degree of one vertex.

Kept on this device only.

Graphs: dots, lines and counting walks

The alphabet

The story: The bridges of a park

Read it

Write it

Build it

Challenges

1 The park, as a table

2 Graph words

3 A tree’s count

4 Two ends to every path

5 Walks of two steps

6 An impossible set of degrees

7 A busy but not too busy park

8 A friend in common

9 The hub

10 Six stations, five tracks

11 Reading the table

12 Five counts

13 Through the middle

14 Close the loop

15 Six spots, two paths each

16 A tree of ten

17 Out and back

18 Three paths from everywhere

19 A triangle somewhere

Tell your own

Download for offline use