Each worksheet prints cleanly on A4 or Letter. Answer keys are on a separate page.

The Lumenary · Grades 3–5

Dots and lines: networks and puzzles

Name: ______________________

Date: ______________________

You will learn to

Decide by experiment which figures can be traced in one stroke without going over a line twice
Find the degree of each dot, and use the handshake rule that the degrees add up to twice the number of lines
Explain why a figure with more than two odd dots can never be traced in one stroke
Find the shortest route in a small road map with distances, and see that it need not use the fewest roads

1.
A network has one centre dot joined by lines to 5 outer dots, and no other lines. What is the degree of the centre dot?
2.
The dots of a network have degrees 3, 3, 2, 4 and 2. How many lines does the network have?
3.
Amaru says he has drawn a network whose four dots have degrees 3, 2, 2 and 2. Is that possible?
- A.Yes — any degrees are possible
- B.No — the degrees add up to an odd number
- C.No — a dot can never have degree 3
4.
Each figure below is connected, and the numbers are the degrees of its dots. Which figures can be traced in one stroke? Select all that apply.
- A.2, 2, 2, 2, 2 (a five-sided loop)
- B.3, 3, 2, 2 (a square with one diagonal)
- C.3, 3, 3, 3 (the envelope)
- D.4, 2, 2, 2, 2 (a bow tie: two triangles sharing a corner)
- E.3, 1, 1, 1 (one dot joined to three others)
5.
A connected figure has five dots with these degrees: P has 2, Q has 3, R has 4, S has 3 and T has 2. Where must a one-stroke tracing start?
- A.At P
- B.At Q or at S
- C.At R, because it has the most lines
- D.Anywhere you like
6.
Ama walks from her house to the swimming pool. The roads are: house–library 4 km, library–pool 5 km, house–park 3 km, park–pool 7 km, park–shop 3 km, shop–pool 2 km. What is the shortest distance from her house to the pool, in kilometres?
7.
The people of Königsberg decide to build new bridges so that a walk crossing every bridge exactly once becomes possible. (The walk may start and finish in different places.) What is the smallest number of new bridges they need?
8.
Lean has checked the theorem odd_dot_is_an_end: if a route traces a network in one stroke, then every odd dot is the start or the end of the route. Which statement can Gideon conclude from this theorem alone?
- A.A network with four odd dots cannot be traced in one stroke.
- B.A network with two odd dots can always be traced in one stroke.
- C.Every network with no odd dots is connected.
- D.The house can be traced starting at the roof top E.
9.
Margaret writes a network as a list of lines, each line a string of two dot letters, like ["AB", "BC", "CA"] for a triangle. Complete the function degree(lines, dot) so that it returns the number of line ends at dot. Two lines may join the same two dots (like bridges).
Computational — Practice

Answer key — Dots and lines: networks and puzzles

1.
Each of the 5 lines has one end at the centre dot and one end at an outer dot. So 5 line ends meet at the centre: its degree is 5. (Each outer dot has degree 1.)
2.
The degrees add up to $3 + 3 + 2 + 4 + 2 = 14$ . By the handshake rule this is twice the number of lines, so there are $14 \div 2 =$ 7 lines.
3.
The degrees add up to $3 + 2 + 2 + 2 = 9$ , an odd number. But in every network the degrees add up to twice the number of lines, which is always even. So no such network exists. Another way to say it: a network always has an even number of odd dots, and Amaru's has just one.
4.
Count the odd dots:
- 2, 2, 2, 2, 2: 0 odd dots — traceable.
- 3, 3, 2, 2: 2 odd dots — traceable (start at a 3, end at the other 3).
- 3, 3, 3, 3: 4 odd dots — impossible.
- 4, 2, 2, 2, 2: 0 odd dots — traceable.
- 3, 1, 1, 1: 4 odd dots — impossible.
So the pentagon, the square with one diagonal and the bow tie can be traced.
5.
The odd dots are Q (degree 3) and S (degree 3). In a one-stroke route every odd dot is the start or the end, and there are exactly two of them, so the route must start at one of Q and S and finish at the other. Since the figure is connected and has exactly two odd dots, such a route really exists.
6.
List every route that does not visit a place twice:
- house → library → pool: $4 + 5 = 9$ km (2 roads)
- house → park → pool: $3 + 7 = 10$ km (2 roads)
- house → park → shop → pool: $3 + 3 + 2 = 8$ km (3 roads)
The shortest is 8 km, and it uses the most roads. Fewest roads is not the same as shortest.
7.
At the moment all four pieces of land have odd degree, so a walk is impossible. A new bridge adds 1 to the degree of each of its two ends. Build one bridge between two odd places — for example from the north bank to the south bank. Then north and south have degree 4, and only the island (5) and the east (3) are odd. Exactly two odd dots in a connected network: now the walk is possible, from the island to the east or back. So the answer is 1.
8.
The theorem says that whenever a one-stroke route exists, every odd dot is its start or its end. A route has one start and one end, so at most two different dots can be odd. Hence a network with four odd dots has no one-stroke route at all. The theorem does not say that routes exist when there are 0 or 2 odd dots — that is the other half of Euler's rule, which is true for connected networks but is a separate theorem.

Look at both ends of every line and count the ones equal to dot:

def degree(lines, dot):
    count = 0
    for line in lines:
        for end in line:
            if end == dot:
                count = count + 1
    return count

For the Königsberg bridges the island I appears at one end of five lines, so degree(..., "I") is 5.