To: Frits G"obel
Date: Fri, 20 Jun 1997 18:30:28 METDST
Subject: CFF 43

Dear Frits,
I just read your article in CFF 43.
I am not satisfied with your drawings
of the graph and the following analysis.
I send you my analysis of your graph
problem. I hope you like it although it
is not for the average CFF-reader.

Yours Torsten


To: Frits G"obel
Date: Fri, 20 Jun 1997 21:05:45 METDST
Subject: CFF 43

Dear Frits,
I just saw a more puzzler like argumentation
for your Hamiltonian path problem.

Yours Torsten
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

                                             Torsten Sillke, 20.06.97
The Hamiltonian paths of a special graph
are searched in:

Frits G"obel,
  Solving a Pentomino Problem with Graph Theory,
  CFF 43, (1997), p4-5

I dislike the drawing of the given graph.
First I cut of the lose ends.
It remains a 8 vertex graph and we are
looking for Hamiltonian path from F to Y.
If I discard Y, I am looking for a path from
F to a vertex in {N,P,T}. 

At last I reduce:

    X           X
    |          / \
    A   to    /   \
   / \       /     \
  X   X     X-------X

for A in {V,W,Z}.
Multiple edges can be discarded, as at most
one can be used without double visiting a vertex.

It remains a K_4 with the vertices {F,N,P,T}.
Now there are 6 = 3! Hamiltonian pathes starting 
at F:

      F---N---P---T
      F---N---T---P
      F---P---N---T
      F---P---T---N
      F---T---N---P
      F---T---P---N

Now try to extend each path by inserting the 
vertices {V,W,Z} into the three edges (and add Y).
This need not be possible, but in this case each
reduced solution extends uniquely (unique matching).

      F-Z-N-W-P-V-T-Y
      F-W-N-Z-T-V-P-Y
      F-W-P-V-N-Z-T-Y
      F-W-P-V-T-Z-N-Y
      F-Z-T-V-N-W-P-Y
      F-Z-T-V-P-W-N-Y

Now connect the lose ends to get all solutions:

      X-F-Z-N-W-P-V-T-Y-U-L-I
      X-F-W-N-Z-T-V-P-Y-U-L-I
      X-F-W-P-V-N-Z-T-Y-U-L-I
      X-F-W-P-V-T-Z-N-Y-U-L-I
      X-F-Z-T-V-N-W-P-Y-U-L-I
      X-F-Z-T-V-P-W-N-Y-U-L-I

2nd approach:
-------------
The alternation between vertices from {F,N,P,T} and
{V,W,Y,Z} is easily seen, as {V,W,Y,Z} is an independent
set. Therefore a Hamiltonian path between F and Y must
be alternating. So wie can discard all edges between
vertices from {F,N,P,T}. After ommitting Y the resulting
graph is very sparse:

               F
              / \
             Z   W
            / \ / \
           T   N   P
            \  |  /
             \ | /
              \|/
               V

All Hamiltonian pathes starting at F end in {N,P,T}
and therefore at Y. Again we find 6 pathes.

------------------------------------------------------------------
To: Torsten
Subject: Re: CFF 43
Date: Wed, 25 Jun 97 10:45:07 METDST

Dear Torsten,

Thank you for your analysis. Iwas
surprised to see that I missed a
solution.

Frits

------------------------------------------------------------------
To: Frits G"obel
Date: Wed, 25 Jun 1997 14:32:05 METDST
Subject: Re: CFF 43

Dear Frits,
you wrote
>
> Thank you for your analysis. Iwas
> surprised to see that I missed a
> solution.
>
the point is not the missing solution
it is the missing analysis.
What do people think is 'Graph Theory'
after reading this article. It seems
that the hole theory is only the
concept is drawing vertices and edges.
I think the article doesn't show
how Graph Theory helps in solving
the problem.

I think we need a reviewing system
for the CFF. In the last issues I found
several little things which I think
should not go in print. E. g. a sentence:
'tomorow I will analyse the remaining cases of
the problem' anoyed my.


I often talked with Wizorke about the
quality of the CFF, but he says that he
as the only german editor should not
insist on changes.

(It is not easy for me to find the right words,
as this is not a mathematical problem.)

Yours Torsten

------------------------------------------------------------------
To: Torsten
Subject: Re: CFF 43
Date: Thu, 26 Jun 97 9:20:04 METDST

Dear Torsten,

My analysis is not missing.
I just didnot write it down
in order to keep the article
short.
You remind me of students who
say 'I have found a completely
different solution',which turns out
to be a variation of the one I have
just showed.
Also, for a simple problem like the
one I treated, graph theory cannot do
much more than drawing a picture to
facilitate the analysis. It is not a
problem where you need a theorem like
Kuratowski's.

With kind regards,

Frits