Applications: Eulerian and Hamiltonian Routes

Model the town as a graph, with a vertex for each junction and an edge for each street. A walk is any sequence of edges, each starting where the last one ended. A trail repeats no edge, a path repeats no vertex, a circuit is a trail that ends where it began, and a cycle is a circuit that repeats no vertex except the one at both ends. So check each log for a repeated street first, then for a repeated junction, and then whether it is closed.

1. Model the town as a graph: a vertex for each junction and an edge for each street. A trail is a walk that uses no edge twice, and a path is a walk that visits no vertex twice. A circuit is a trail that ends where it began, and a cycle is a circuit that visits no vertex twice except the one it starts and ends at.
2. List Monday's streets in order: A–B, B–C, C–D, D–E, E–B and B–F. These are 6 different streets, so no street is repeated and the route is at least a trail.
3. (a) Monday's route reaches B twice, once from A and again from E, so it is not a path. It starts at A and ends at F, so it is not closed either. The most precise word is trail, and junction B decides it.
4. List Tuesday's streets in order: A–F, F–B, B–C, C–E, E–D, D–C, C–B and B–A. The van drove 8 times along a street, but B–C and C–B are the same street, so it used only 7 different streets.
5. (b) Street B–C was driven twice, so the route is not a trail, and therefore not a circuit or a cycle, even though it ends at A where it began. The most precise word is walk (a closed walk), and street B–C broke the rule. Check: every other street in Tuesday's list appears exactly once.

answer(a) A trail: its 6 streets are all different, but it reaches junction B twice, so it is not a path, and it ends at F rather than A; (b) no: street B–C was driven twice, so the van used only 7 different streets in 8 drives, and the route is a closed walk, not a circuit

techniqueWalks, Trails, Paths, Circuits and Cycles

Model the museum as a graph, with a vertex for each room and an edge for each doorway. The patrol is classified by whether it repeats a doorway, repeats a room, and returns to its start. A short tour is a cycle of length 4 through H, and the cycles are counted by choosing the two galleries next to the hall.

1. Model the museum as a graph: a vertex for each room and an edge for each doorway. The patrol goes through the doorways H–A, A–B, B–D, D–C, C–B and B–H, which are 6 different doorways.
2. (a) No doorway is used twice and the patrol ends in H, where it began, so it is a circuit. It passes through gallery B twice, so it is not a cycle. The most precise word is circuit, and room B decides it.
3. A short tour is a cycle of length 4 through H: the hall, a gallery x, a gallery y, a gallery z, and back to the hall. So x and z must both have a doorway to H, which means they are two of A, B and C, and y must have a doorway to each of them.
4. Take each pair of galleries next to the hall in turn. A and B both open into D, which gives H–A–D–B–H. A and C both open into B and into D, which gives H–A–B–C–H and H–A–D–C–H. B and C both open into D, which gives H–B–D–C–H.
5. (b) There are 4 tours. Each pair was taken once, so a tour and its reverse, which has the same two galleries next to the hall, are counted once. Check: D has no doorway to the hall, so it can only be the middle gallery, and it is the middle gallery in three of the four tours.

answer(a) A circuit: its 6 doorways are all different and it returns to H, but it passes through room B twice, so it is not a cycle; (b) 4 tours: H–A–D–B–H, H–A–B–C–H, H–A–D–C–H and H–B–D–C–H

techniqueWalks, Trails, Paths, Circuits and Cycles

Model the village as a graph, with a vertex for each junction and an edge for each street. A route that drives every street exactly once is an Eulerian trail. Each time the route passes through a junction it uses two streets there, one in and one out, so only the start and the finish can have an odd number of streets.

1. Model the village as a graph: a vertex for each junction and an edge for each street. A route that drives every street exactly once is an Eulerian trail, and the degrees decide whether one exists and where it can start and finish.
2. Count the streets at each junction: S has 6, A, D, E and F have 2 each, and B and C have 3 each. Every time the plow passes through a junction it uses one street in and one street out, so a junction where the route neither starts nor finishes has an even degree.
3. (a) Only B and C have odd degree, and the graph is connected, so an Eulerian trail exists, and it must start at one of B and C and finish at the other. For example, B–A–S–B–C–S–E–F–S–D–C drives all 10 streets once each.
4. The square is not an end of the route, so every pass through it uses 2 of its 6 streets, one to arrive and one to leave.
5. (b) The plow passes through the square 6 ÷ 2 = 3 times. Check with the route in (a): it passes through S between A and B, between C and E, and between F and D.

answer(a) At B and C, the only 2 junctions with an odd number of streets: the route starts at one and finishes at the other; (b) 3 times

techniqueEulerian Trails and Circuits

Model the park as a graph, with a vertex for each junction and an edge for each road. A closed route that drives every road exactly once is an Eulerian circuit, which needs every degree to be even. Driving a road a second time adds 1 to the degree at each of its ends, so the repeated roads must join the odd junctions in pairs, as cheaply as possible.

1. Model the park as a graph: a vertex for each junction and an edge for each road. A route that drives every road exactly once and returns to its start is an Eulerian circuit, which exists only when every degree is even.
2. (a) Count the roads at each junction: A, B, D and F have 3 each, and C and E have 2 each. The 4 junctions A, B, D and F have odd degree, so no closed route can drive every road exactly once.
3. Driving a road a second time adds 1 to the degree at each of its ends. The repeated roads must therefore join the odd junctions in two pairs. Four junctions can be paired in three ways, and for each pair count the fewest roads between the two junctions.
4. A with B and D with F: 1 + 2 = 3 roads, since D and F are two roads apart. A with D and B with F: 1 + 1 = 2 roads. A with F and B with D: 1 + 2 = 3 roads, since B and D are two roads apart.
5. (b) The fewest is 2 roads: the truck drives A–D and B–F a second time. Then A, B, D and F each have degree 4, and every degree is even. Check with a route from the depot: C–B–F–B–A–D–A–F–E–D–C drives all 8 roads and repeats only B–F and A–D, 10 drives in all.

answer(a) A, B, D and F, the 4 junctions with an odd number of roads; (b) 2 roads, A–D and B–F

techniqueEulerian Trails and Circuits

Model the park as a graph, with a vertex for each junction and an edge for each path. A course that runs every path exactly once is an Eulerian trail. In a connected graph such a trail runs between two different vertices exactly when those two are the only vertices of odd degree, and a new path adds 1 to the degree at each of its ends.

1. Model the park as a graph: a vertex for each junction and an edge for each path. A course that runs every path exactly once is an Eulerian trail. In a connected graph it can run from one vertex to a different one exactly when those two are the only vertices of odd degree.
2. Count the paths at each junction: P has 3, Q has 2, R has 3, S has 4, T has 2 and U has 4. The only junctions with odd degree are P and R.
3. (a) No. Q has even degree, so a course that runs every path once cannot finish there. A course that starts at P must finish at the other odd junction, R.
4. A new path adds 1 to the degree at each of its ends. For P and Q to be the only odd junctions, R must become even and Q must become odd, so the new path must join R and Q, which are not yet joined.
5. (b) Cut the new path between R and Q. Then R has degree 4, Q has degree 3, and the only odd junctions are P and Q. Check with a course: P–S–Q–U–P–T–R–S–U–R–Q runs all 10 paths once each and finishes at the village hall.

answer(a) No: P and R are the only junctions with an odd number of paths, 3 each, so a course that starts at P must finish at R, not at the village hall; (b) between R and Q, which gives a course over all 10 paths from P to Q

techniqueEulerian Trails and Circuits

Model each logo as a graph, with a vertex for each labeled point and an edge for each line. One stroke that draws every line once is an Eulerian trail, and if it ends where it began it is an Eulerian circuit. A stroke passes through a point using its lines in pairs, so a point where an odd number of lines meet must be the end of a stroke.

1. Model each logo as a graph: a vertex for each labeled point and an edge for each line. One stroke that draws every line once is an Eulerian trail; if it ends where it began, it is an Eulerian circuit.
2. First logo: count the lines at each point. A, B, C and D each meet 4 lines (two sides of the square, half a diagonal and a side of a triangle), X meets 4, and E and G meet 2 each.
3. (a) Every degree is even and the logo is connected, so it has an Eulerian circuit. Yes, it can be drawn in one stroke, and the stroke must end where it began, because a stroke that ended somewhere else would leave its two ends with an odd number of lines. One such stroke is A–B–C–D–A–X–C–E–D–X–B–G–A.
4. Second logo: the corners meet 2 lines each, the center S meets 4, and the middles N, P, Q and R meet 3 each. There are 4 points of odd degree.
5. A stroke passing through a point uses its lines in pairs, so each odd point must be an end of some stroke. A stroke has only two ends, so 4 odd points need at least 4 ÷ 2 = 2 strokes.
6. (b) Two strokes are enough: N–S–Q–L–P–K–N–J–R–M–Q, which draws 10 lines, and then P–S–R, which draws the last 2. The fewest is 2 strokes.

answer(a) Yes: every point meets an even number of lines, 4 at A, B, C, D and X and 2 at E and G, so all 12 lines can be drawn in one stroke, and the stroke must end where it began; (b) 2 strokes, because the 4 middles of the sides each meet 3 lines

techniqueEulerian Trails and Circuits

Model the cities as a graph, with a vertex for each city and an edge for each direct line. A tour that plays every city once is a Hamiltonian path, and a round trip is a Hamiltonian cycle. No degree test settles either one, so the orders are built city by city, and a city with only two lines forces both of them into a cycle.

1. Model the cities as a graph: a vertex for each city and an edge for each direct line. A tour that plays every city once is a Hamiltonian path, and a round trip is a Hamiltonian cycle. There is no degree test for either, so build the orders city by city.
2. H has lines only to C and E, so the second city is C or E. From C the next city is D or E; F cannot come yet, because it must be last. C then D forces D then B, then E, then F: H–C–D–B–E–F. C then E forces E then B, then D, then F: H–C–E–B–D–F.
3. From E the next city is B or C. E then B forces B then D, and D then C, then F: H–E–B–D–C–F. E then C forces C then D and D then B, but B's lines run only to D and E, which are already played, so that branch fails.
4. (a) There are 3 orders: H–C–D–B–E–F, H–C–E–B–D–F and H–E–B–D–C–F.
5. For a round trip, H has only two lines, so the trip leaves along one and returns along the other. The rest of the trip is a path from C to E through B, D and F. B has only the lines to D and E, so the path must end D, B, E, and the city between C and D is F.
6. (b) There is 1 round trip: H–C–F–D–B–E–H. Check each step: H–C, C–F, F–D, D–B, B–E and E–H are all direct lines.

answer(a) 3 orders: H–C–D–B–E–F, H–C–E–B–D–F and H–E–B–D–C–F; (b) 1 round trip, H–C–F–D–B–E–H

techniqueHamiltonian Paths and Cycles · Walks, Trails, Paths, Circuits and Cycles

Model the guests as a graph, with a vertex for each guest and an edge for each pair who know each other. A seating in which everyone knows both neighbors is a Hamiltonian cycle. A guest who knows only two others must sit between exactly those two, and those forced neighbors fix most of the circle.

1. Model the guests as a graph: a vertex for each guest and an edge for each pair who know each other. A seating in which everyone knows both neighbors is a Hamiltonian cycle.
2. Bea knows only Amir and Chen, so they must be her two neighbors: Amir, Bea, Chen sit together in that order. In the same way Emil knows only Dina and Farah: Dina, Emil, Farah sit together.
3. Join the two groups of three into one circle. Chen, at one end of the first group, must sit next to Dina or Farah. Chen knows Dina but not Farah, so Chen sits next to Dina, and then Farah sits next to Amir, whom she knows.
4. (a) The order round the table is Amir, Bea, Chen, Dina, Emil, Farah, and back to Amir, and this is the only seating: 1 seating. The pairs Amir and Chen, and Dina and Farah, know each other but do not sit together.
5. Gus knows only Chen and Farah, so he must sit between them. Bea still needs Amir and Chen, so Chen's other neighbor is Bea, and Amir comes after Bea. Emil still needs Dina and Farah, so Farah's other neighbor is Emil, and Dina comes after Emil.
6. (b) No. The only order left is Gus, Chen, Bea, Amir, Dina, Emil, Farah, which puts Amir next to Dina, and they do not know each other. So there are 0 seatings for the seven.

answer(a) Amir, Bea, Chen, Dina, Emil, Farah round the table, and it is the only seating: 1; (b) No, 0 seatings: Gus must sit between Chen and Farah, Bea between Amir and Chen, and Emil between Dina and Farah, which leaves Amir next to Dina, and they do not know each other

techniqueHamiltonian Paths and Cycles

Model the islands as a graph, with a vertex for each island and an edge for each route. The round trip is a Hamiltonian cycle. No test says that one exists, but two facts can rule one out: a vertex of degree 1, and a cut vertex, one whose removal disconnects the graph.

1. Model the islands as a graph: a vertex for each island and an edge for each route. The round trip is a Hamiltonian cycle, which arrives at and leaves every island once, using two of its routes.
2. Z has only one route, to U. A cycle through Z would have to arrive and leave along that one route, and a cycle cannot use an edge twice.
3. (a) No: Z has degree 1, so no round trip can call at Z and carry on.
4. After the new route, Z has degree 2, and every island has at least 2 routes: M has 4, P, R, S and U have 3 each, and Q and Z have 2 each. The degrees no longer rule the trip out. Now remove M: P, Q and R are left joined only to one another, and S, U and Z only to one another.
5. (b) No: M is a cut vertex. The only routes between the group P, Q, R and the group S, U, Z pass through M, so a trip that calls at both groups must pass through M between them as well as start and finish there. It would visit M twice, which a Hamiltonian cycle does not allow.

answer(a) No: Z has only 1 route, to U, so a trip cannot arrive at Z and leave again; (b) No: M is a cut vertex, since removing it splits the islands into 2 groups, P, Q, R and S, U, Z, so the trip would have to pass through M twice

techniqueHamiltonian Paths and Cycles

Model the cities as the complete graph on six vertices, with an edge for every pair. A round trip that visits every city once is a Hamiltonian cycle. Fixing the start at H and ordering the other cities counts each cycle twice, once in each direction. The trips that use one particular flight are counted by fixing that flight and ordering the rest.

1. Model the cities as the complete graph K₆: a vertex for each city and an edge for every pair. A round trip that visits every city once is a Hamiltonian cycle.
2. Start every trip at H. The five client cities can then be visited in 5! = 5 × 4 × 3 × 2 × 1 = 120 orders, and each order gives a round trip back to H.
3. Each round trip appears twice among these orders, once in each direction: for example, H–K–L–M–N–V–H and H–V–N–M–L–K–H are the same trip.
4. (a) There are 120 ÷ 2 = 60 round trips. This is (n − 1)!2 with n = 6.
5. Count the trips that use the flight between K and L. Write each one starting K, L, followed by the other four cities, H, M, N and V, in some order, and back to K. There are 4! = 24 such orders, and each trip through K–L is written exactly once this way, since its reverse starts L, K.
6. (b) The trips left are those that do not use K–L: 60 − 24 = 36 round trips. Check: each trip uses 6 of the 15 flights, and by symmetry each flight is used by the same number of trips, 60 × 615 = 24.

answer(a) 60 round trips; (b) 36 round trips

techniqueHamiltonian Paths and Cycles