1. ## Transversing Paths

Hi, here I have a problem with how to travel across a shape without going alone the same line twice. Capitalization and 'lower case-alization' of single letters (except I) are intentional in this question. Capitals represent a destination, lower case represents a path between two destinations.

In question 1) below, a path of c, b*, b, c* will start at 'B', follow path 'c' etc and follow 'c*' back to B. This means it uses 4 paths.

1)

What is the longest trail possible on this and why does it need to start on 'B' or 'C'?

2)

Prove that the longest track possible is '5', when you start at 'A'

3)

What is the longest continuous trail possible, justifying your reason.

Thanks for any help and advice.

2. You can divide the points into three types: the point where you start, the point where you stop, and the points you just pass through.
It takes two paths to pass through a point which means that any point that you "just pass through" must have an even number of paths leading to it. The point you start at must have the one path through which you leave and then an even number of paths you "pass through" on- an odd number of paths total. Similarly, the point you end at must have the one path through which you enter and then an even number of paths you "pass through" on- an odd number of paths total. An exception to that is if you start and end at the same point: then that point also must have an even number of paths connected to it. There can be, of course, at most one point at which you start and one point at which you end.

That leads to the conclusion of Euler's famous analysis of the "Konigsberg bridges" problem- such an "Euler circuit" of a graph is possible if and only if the number of nodes of odd degree- that is, the number of points with an odd number of bridges connected- is either 0 or 2.

In your problem (1), B and C both have degee 3 while A has degree 4 so this is possible. Any circuit must start at either B or C because, as I said, with an odd degree we cannot only "pass through"- that would require an even number of bridges. We must start at one and end at the other. And it is easy to find such a circuit that uses all paths. Indeed, for the example you give, "a path of c, b*, b, c* will start at 'B', follow path 'c' etc and follow 'c*' back to B", just add a to make make a circuit that uses all 5 paths.

In problem (2), A, B, C, and D all have degree 3 so a complete circuit is impossible. But it is easy see that the path A, C, D, A, B, D covers every path except BC.

In problem (3), A, B, C, G, H, and I all have degree 3 so a complete circuit is possible. It looks to like the best you could do is, say start at A, go around the "loop", B, C, A, out to D, around E, F, D, then out to G, then around H, I, G, using all paths except the 4 other "radial" paths.