Networks/graph theory

problem
Favourite

Tourism

Age

11 to 16

Challenge level

2 out of 3

If you can copy a network without lifting your pen off the paper and without drawing any line twice, then it is traversable. Decide which of these diagrams are traversable.
problem
Favourite

Limiting Probabilities

Age

16 to 18

Challenge level

3 out of 3

Given probabilities of taking paths in a graph from each node, use matrix multiplication to find the probability of going from one vertex to another in 2 stages, or 3, or 4 or even 100.
problem

Plum Tree

Age

14 to 18

Challenge level

1 out of 3

Label this plum tree graph to make it totally magic!
problem

W Mates

Age

16 to 18

Challenge level

1 out of 3

Show there are exactly 12 magic labellings of the Magic W using the numbers 1 to 9. Prove that for every labelling with a magic total T there is a corresponding labelling with a magic total 30-T.
problem

Only Connect

Age

11 to 14

Challenge level

1 out of 3

The graph represents a salesman’s area of activity with the shops that the salesman must visit each day. What route around the shops has the minimum total distance?
problem

Travelling Salesman

Age

11 to 14

Challenge level

1 out of 3

A Hamiltonian circuit is a continuous path in a graph that passes through each of the vertices exactly once and returns to the start. How many Hamiltonian circuits can you find in these graphs?
problem

Maximum Flow

Age

16 to 18

Challenge level

1 out of 3

Given the graph of a supply network and the maximum capacity for flow in each section find the maximum flow across the network.
problem

Magic Caterpillars

Age

14 to 18

Challenge level

3 out of 3

Label the joints and legs of these graph theory caterpillars so that the vertex sums are all equal.
problem

Networks and Nodes

Age

7 to 11

Challenge level

2 out of 3

Without taking your pencil off the paper or going over a line or passing through one of the points twice, can you follow each of the networks?
problem

Redblue

Age

7 to 11

Challenge level

3 out of 3

Investigate the number of paths you can take from one vertex to another in these 3D shapes. Is it possible to take an odd number and an even number of paths to the same vertex?