[r-t] in-course 120

[Philip Saddleton]

edward martin said  on 04/10/2006 19:51:
> On 10/4/06, Andrew Johnson <andrew_johnson at uk.ibm.com> wrote:
>
>   
>> With a bit of experimentation I came up with
>> 3.1.3.5.1.3.5.1.3.5.3.1.3.1.3.5.1.3.5.1.3.5.3.5
>>
>> which has some nice symmetry.
>>     
>
> Very nicely done. I too had a look at Stedman Doubles but failed to
> spot the route that you found
>
> mew
>   

I think this and its reverse are the only possible 5-parts. Here's the 
graph (view in a fixed font):

. a=======k
. |       |
. |  c-d  |
. | /| |\ |
. |/ f-e \|
. b  | |  l
.  \ g-h /
.   \| |/
.    j-i

We need to visit each vertex twice, with an odd number of edges between 
each visit. We cannot revisit any of c-j without passing through b or l, 
as all circuits in this subgraph are even. Clearly we cannot follow the 
same edge twice in succession. Vertices a and k must be between b and l, 
so the only options are

l-k-a-b...b-a-k-l... or l-k-a-b...l-k-a-b...

where ... are chosen from c-j. But as there are only two ...'s and 
neither has any repeats, each contains each of c-j once. This means we 
can only have the first option, or the l-k-a-b are revisited after an 
even number of edges. Now what possibilities are there for b...b. We 
start with c and finish with j, or vice versa - one will simply be the 
reflection of the other. The only possibilities that visit all of the 
vertices is

b-c-d-e-f-g-h-i-j (or its reverse)

and for l..l

l-d-c-f-e-h-g-j-i-l (or its reverse)

once we choose the direction of one there is only one possibility for 
the other, giving the path

a-b-c-d-e-f-g-h-i-j-b-a-k-l-d-c-f-e-h-g-j-i-l-k-a

This is Andrew's result. You can now go back and label all of the edges 
with their place notation. the double link between a and k can be 1 or 
5: one of each is needed, or it comes round after one part.

pabs