A Polynomial time Algorithm for Hamilton Cycle with Degree 3

Lizhi Du
College of Co mputer Science and Technology, Wuhan University of Science and Technology,
Wuhan, 430065, P.R. of Ch ina
Email: edw95@yahoo.com
Tel: 86 13554171855

Abstract At present, most effective algorithms to find a Hamilton circle in an undirected graph
are generally based on the Rotation-Extension method developed by Posa. However, due to the
deficiencies of Posa's method, such algorithms are mostly useful for very dense graphs. This article
introduces a method called Enlarged Rotation-Extension that modifies and extends Posa's
method, overcoming its deficiencies. Based on this technique, the algorithm is polynomial and we
give a detailed proof for it.
Keywords: Computational Complexity; Computer Algorithm; Hamilton Cycle; Hamilton Path;
Polynomial Time

. Introduction
A Hamilton path is a path between two vertices of a graph that visits each vertex exactly once. A
Hamilton path that is also a cycle is called a Hamilton cycle.
Finding Hamilton cycles (paths) in simple undirected graphs is a classical NP Complete problem,
known to be difficult both theoretically and computationally, so we cannot expect to find polynomial
time algorithms that always succeed, unless NP P .[1][2]
Over the past decades, the Hamilton cycle (path) problem has been extensively studied. One
direction of these studies is to find a sufficient condition for a graph to be Hamiltonian (when there is at
least one Hamilton Cycle in a graph, we say that this graph is Hamiltonian). Most of these conditions for
a general graph depend on the number of edges of the graph. Using these techniques, a graph is usually
provably Hamiltonian only if there are sufficiently many edges in the graph [3][4][5]. In other words, these
techniques are not useful for sparse graphs. Another direction is to design a random algorithm which can
succeed in finding Hamilton cycles or paths with high probability, or works well only for some classes
of graphs. The problem for these random algorithms still is: all these methods work only for much
denser graphs or some sparse but regular graphs [6][7][8][9][10] , not directly useful for general graphs,
especially sparse graphs.
For finding Hamilton cycles (paths), the most well-known method is the rotation-extension
technique, which is developed by Posa [8]. In fact, most of the current existing random algorithms are
based on the rotation-extension technique. Due to the inherent limitation of this method, all these
random algorithms can only work well for very dense graphs. So if we can overcome the
rotation-extension techniques immanent deficiency, it is possible for us to get a n efficient random
algorithm or even a polynomial time algorithm for general graphs.
We developed a method which we call an enlarged rotation-extension technique. This technique
can overcome Posas deficiency. Our method contains all advantages of the rotation-extension technique
but utterly enlarges its functions. Based on this method, we get a polynomial time algorithm for the
Hamilton cycle problem and we give a detailed proof for the graphs with vertex degree 3.
. The Rotation-Extension technique and its main deficiency

Suppose we have a path P x0 x1 ...xk in a graph G and we wish to find a path of length k 1 . If x 0
or x k has a neighbor not in P, then we can extend P by adding the neighbor. If not, suppose x k has a
neighbor xi , where 0 i k 2 . If i 0 and G is connected, then there is an edge e ( x j , w)
joining the cycle x0 x1 ...xk x0 to the rest of the graph, and so the path wx j x j 1 ...xk x0 ...x j 1 has length
k 1. This is called a cycle extension. We call the two vertices x 0, xk key vertices of the extension. If
i 0 , then we construct the path x0 x1 ...xi x k xk 1 ...xi 1 of length k with a different end point x i 1 and
look for further extensions. This is called a rotation, or a simple transform. We call the vertex x k the key
vertex of the rotation. This is Posas Rotation-Extension technique.
The main deficiency of this method is: the rotation or extension is performed at a fixed place, in
order to always fulfill the condition for the rotation or extension, the graph must have dense edges. So
this technique is not applicable for sparse graphs.

. Algorithm

Definitions:
For an undirected graph G with n vertices, a broad cycle is defined as a cyclic sequence
x1 , x 2 ,..., x n , x1 of the vertices of G where every pair xi , xi 1 may or may not be adjacent in G. We call a
pair ( xi , xi 1 ) (including ( x n , x1 ) ) of non-adjacent vertices a break consecutive pair or a break. So the
number of break consecutive pairs is between 0 and n for a broad cycle. Obviously, a break consecutive
pair is constituted by two vertices (say vertices a and b, we call such a vertex a break side vertex). We
use a * b to denote this break consecutive pair. If two consecutive vertices a and b are adjacent, we call
them connecting consecutive pair, we use ab to denote this connecting consecutive pair. We use
a...b to denote that there are some other vertices between a and b. For an undirected graph with n
vertices, the number of all possible different break consecutive pairs and connecting consecutive pairs is
n(n 1)
. A break consecutive pair or a connecting consecutive pair is also called a consecutive pair.
2
A segment: in a broad cycle, we call one or more consecutive vertices a segment (may contain one
or more breaks). So, in a broad cycle, any vertices sequence between two non-consecutive vertices is a
segment, and there are n(n 1) different segments in a broad cycle for an n vertices graph.
For convenience, we only consider the un-directed graphs whose each vertex has degree 3, because
this problem is also an NP complete problem [21].
Suppose that vertex a is adjacent to vertices b, c, d, for vertex a we have three connecting
consecutive pairs: ba, ca, da . For another vertex e, it is adjacent to f, g, h, we also have such three
connecting consecutive pairs. For the consecutive pair (a, e), we can construct 9 different segments:
ba * ef , ba * eg , ba * eh,... For each segment, we can construct a broad cycle which contains this
segment. We call this segment the broad cycles main segment. We also say that the broad cycle is this
main segments broad cycle. We call the consecutive pair (a, e) the segments core consecutive pair. It
is also this segments broad cycles core consecutive pair. Call vertex a or e a core vertex of this broad
cycle or of the main segment. Each core consecutive pair has up to 9 main segments. The 9 segments
and their 9 broad cycles have the same one core consecutive pair. Also we call each of these 9 broad
 n(n 1)
cycles the consecutive pair (a, e)s one broad cycle. Because for an n vertices graph, there are
2
9 n(n 1)
different vertex pairs, we can construct up to (in fact less than) broad cycles (some of them
2
might be duplicates). Please note that the core consecutive pair (a, e) has to be a break, i.e., vertex a is
not adjacent to vertex e, and we call this break the main segments break or the main break.
A main segment contains four vertices. A vertex pair has up to 9 different main segments and has
up to 9 different broad cycles.
For each vertex, we call all such broad cycles whose core consecutive pairs contain this vertex this
vertexs broad cycles. In an n-vertex graph, every vertex has up to 9 * (n 1) broad cycles.
We call all edges incident upon a vertex this vertexs edges. So for a graph with degree 3, a vertex
has 3 edges, and in any broad cycle, a vertexs edges cannot be more than 2. Also we call an edges two
end vertices this edges vertices.
For a broad cycle, cut a segment at a place and insert the segment between two consecutive vertices
in some other place of the broad cycle. We call this operation a cut and insert. The main operation in
our algorithm is the cut and insert, now we explain it. First we define the basic cut and insert: let
x1 , x 2 ,..., x n , x1 (note: we use the , to separate two vertices, because they may be adjacent to each other
or may not) denote a broad cycle, let S xi , xi 1 ,..., xi r be a segment of this broad cycle, and let j be an
index such that x j and x j 1 are not in S. A broad cycle C is obtained by cutting S and inserting it into
x j and x j 1
if either C1 x j , xi , xi 1 ,..., xi r , x j 1 , x j 2 ,..., xn , x1 ,..., x j 1 , x j ,
or C2 x j , xi r , xi r 1 ,..., xi , x j 1 x j 2 ,..., xn , x1 ,..., x j 1 , x j (addition is meant modulo n).
This is a basic cut and insert. We can see that in the process of this basic cut and insert, we get three
(or two in some special cases) newly produced consecutive pairs. Each of these three consecutive pairs
has two sides. We call S the key segment of this cut and insert. If Ss two end vertices are adjacent, we
can do an extension on S and then insert it. So, a cut and insert has two cases: 1) only one basic cut and
insert, 2) if Ss two end vertices are adjacent, do an extension on S and then insert it. We take an example
to explain. Let a broad cycle be: abcdefghijkl*mnopa (in the ends the two a mean a cycle, in fact there
is only one vertex a), we cut a segment ijkl, insert it between vertex d and e, we get this broad cycle:
abcd*ijklefghmnopa, this is the case 1). The three new produced consecutive pairs are: d*i, le, hm. Then
the case 2): suppose il is an edge, do an extension on the segment ijkl, and we get: ilkj, jilk, kjil, and then
try to insert each of them in other places of the broad cycle separately. And so on. The key segment is
important. We explain it. For the above broad cycle, kl*mn is the main segment. If mh is an edge, there
are 2 key segments: ijkl, or hijkl. For the former one, we have to insert it into another place and if the
two end vertices il are adjacent we can do an extension before to insert. For the later one, we only can do
a rotation. For this rotation, we also can see the key segment still is ijkl, and we insert it between gh. So
ih has to be an edge. Due to the degree 3, a broad cycle has up to 8 key segments. There is another kind
of key segments: if mp is an edge, no matter vertex a is adjacent to l or not, the mnop is a key segment.
We first do an extension on it and then insert it into some place. Please note: at least one end vertex of
the inserted segment has to be adjacent to one of the two vertices in the inserting place.
We call all the current broad cycles old broad cycles. If after a cut and insert on broad cycle A, we
get a broad cycle B which contains a main segment whose old broad cycle has more breaks than B or
there is no broad cycle of this main segment before, we call B this main segments new broad cycle,
and call this cut and insert a useful cut and insert. Call this new broad cycle the useful cut and inserts
new broad cycle and call its main segment the useful cut and inserts new main segment. But how to get
a new broad cycles main segment? If there are newly produced breaks, we only check the several
segments of four vertices which B has but A does not have. Otherwise, we have to check other segments
of four vertices which contains one break in A (also in B) by memory (this is not hard to do, though a
main segment may be contained in many broad cycles). So the time is O(1) for each new broad cycle to
decide its main segment (by memory).
The number of vertices is even (because each vertex degree is 3). In a broad cycle, if a vertexs two
consecutive vertices beside it both are not adjacent to it, we call it an isolated vertex. We prescribe that
all the broad cycles do not contain isolated vertices. For the first broad cycle, we can easily get this and
later each useful cut and insert cannot produce an isolated vertex.
Because of no isolated vertices in the broad cycle, at each break s two sides, there are two adjacent
vertex pairs. We call these four vertices a break segment. For example ab*cd is a break segment and ab
or cd is a (break) side vertex pair. Vertex c or d is a break side vertex. We prescribe that when we
re-permute a broad cycle or do a useful cut and insert on it, any other break segment cannot be destroyed
unless the break disappears after a useful cut and insert.
Please note that: each cut and insert must cut from the break of the main segment, i.e., the new
broad cycle does not contain the break of the old main segment; at least one vertex of this break must
become non-break vertex in the new broad cycle; the new main segment of a new broad cycle must be a
new-produced break segment (i.e., the old broad cycle does not contain this segment and the break)
unless there are no new breaks. If there are more than one new produced breaks, we choose one of them
as the new main segment. If after a useful cut and insert we get a broad cycle which does not have
new-produced breaks (new-produced main segment), we can choose one break segment in the new
broad cycle as the main segment which contains one produced break or choose any one if without such a
break. If after a cut and insert on a k breaks broad cycle, we get a broad cycle with two new produced
breaks (i.e., it seems that we have two new main segments, we call one of them which contains one side
vertex pair of the old main segment a quasi- main segment and call the other one additional main
segment.), and suppose that this new broad cycle has k+1 breaks, we choose the quasi- main segment as
the new main segment and it cannot repeat with k+1 breaks (i.e., if such a main segment with k+1 or less
breaks already exists, this cut and insert is not a useful cut and insert.). The additional main segment
may repeat or may not repeat a former main segment with the same (or less) number of breaks. But we
first have to try to get one which does not repeat. And later, any new main segment of a k+1 breaks
broad cycle cannot be the same as the quasi- main segment and its descendants. So, there are two kinds
of additional main segments: the first kind which does not repeat; the second kind which repeats. Only
the first kind of additional main segment can be as a main segment later.
If we can do a useful cut and insert on a main segments broad cycle C to get a new broad cycle, we
say that this broad cycle C has a useful cut and insert for this new broad cycle. Let this new broad
cycles main segment be P, we say that this broad cycle C has a useful cut and insert for this main
segment P and we call C a useful broad cycle. A broad cycle may have more than one useful cut and
insert as well as to get more than one new broad cycle, but each time we get one.
If one cut and insert breaks the core consecutive pair or the main segment, this does not matter,
because we may get another main segments new broad cycle.
Then, our algorithm includes some steps. We call each cut and insert a step and call each useful cut
and insert a useful step. Because we may need to try a lot of cut and inserts on many broad cycles, and
try to get one useful cut and insert on one broad cycle, we call the process (all these cut and inserts) to
try to get a useful cut and insert a big step (later we will prove that at each big step we always can get a
useful cut and insert). At each useful step, we do a useful cut and insert on a main segments (say main
segment r) broad cycle to get a main segments (say main segment g) new broad cycle and this new
broad cycle has less break consecutive pairs than gs old one (if exists). These two main segments are
different. Then we use the new broad cycle to replace the gs old one (i.e., to delete the gs old broad
cycle if it exists). Do the process continually until we get a Hamilton cycle.
We can see that our technique contains all advantages of the rotation-extension technique and the
rotation-extension is only one special case of ours. So, we call ours the enlarged rotation-extension
technique. We will give the precise algorithm later.
Now, we show different useful cut and inserts.
After a useful cut and insert on a broad cycle 1, we get a new broad cycle 2. We call an edge which
is in broad cycle 2 but not in broad cycle 1 a coming edge of this useful cut and insert, and an edge
which is in broad cycle 1 but not in broad cycle 2 a gone edge of this useful cut and insert. We call a
consecutive pair which is in broad cycle 2 but which is not consecutive in broad cycle 1 a coming
consecutive pair of this useful cut and insert, and a consecutive pair which are in broad cycle 1 but are
not consecutive in broad cycle 2 a gone consecutive pair of this useful cut and insert. Also we have
gone edges, gone breaks and coming breaks (new breaks, new produced breaks). We call the main
segment of broad cycle 1 a used main segment after this useful cut and insert.
We have the following kinds of useful cut and inserts:
Kind 1: a rotation. The broad cycle: xabcdefg*hij, fg*hi is its main segment, at least one of ag,
bh is an edge. This time we can get a new broad cycle by a rotation on the segment bcdefg.
Kind 2: an extension. In kind 1, if ag is an edge, we do an extension on abcdefg, then put it
between x and h (all possible segments, at least one is adjacent to x or h).
Kind 3: a cut and then insert. The broad cycle L1 : abcdefg*hijklnzopquv*w, fg*hi is its
main segment, ah, gz are edges, this time we can get a new broad cycle by cutting and inserting the
segment bcdefg between nz. The new main segment is ln*bc (or cb*op). Please note the special case that
nb is also an edge and the number of breaks minus one after this useful cut and insert. The other special
case of this kind: one (or more) gone consecutive pair are not adjacent (i.e., a break), then after this
useful cut and insert, the new broad cycle has less breaks.
Kind 4: a cut, do extension and then insert. The broad cycle: abcdefg*hijxyz, fg*hi is its
main segment, bh and cg are edges, dx is also a edge, this time we can get a new broad cycle by cutting
and inserting the segment cdefg (do extension on it) between xy (that x is not adjacent to y does not
matter) or other place. We call the segment fe*yz or gc*yz an additional segment. Or if ey (or cy) is an
edge and bh is not an edge, the new main segment is ab*hi. Or both ey (or cy) and bh are edges, there
are no new breaks.
Kind 5: a cut, do extension and then insert with two ne w breaks. A broad cycle with k breaks:
abcdefg*hijxyz, fg*hi is its main segment, cg is an edge, dx is also a edge. This time, we can get a
new broad cycle by cutting and inserting the segment cdefg (do extension on it) between xy (that x is not
adjacent to y does not matter) or other place. We call ab*hi a quasi- main segment. Call fe*yz (or gc*yz)
an additional main segment and we choose the quasi- main segment as the new main segment of the new
broad cycle. Suppose that this new broad cycle has k+1 breaks, the new main segment cannot repeat
with k+1 breaks (i.e., if such a main segment with k+1 or less breaks already exists, this cut and insert is
not a useful cut and insert.). The additional main segment may repeat or may not repeat a former main
segment with the same (or less) number of breaks. But we first have to try to get one which does not
repeat. An additional main segment in kind 4 is also as this. And later, any new main segment of a k+1
breaks broad cycle cannot be the same as the quasi- main segment and its descendants. Please note the
special case: there is no additional break, i.e., ey (or cy) is a good edge. This does not affect our later
proof. Please note: for this kind, usually we can get one quasi- main segment with many different
additional main segments, but we only choose one of them (i.e. for each new quasi- main segment, we
get a new broad cycle).
We will prove that: at each big step, if there is at least one Hamilton cycle in this graph and we have
not got one yet, we always can have a useful cut and insert to get a main segments new broad cycle,
until we get a Hamilton cycle at last.
Our algorithm supposes that the graph contains at least one Hamilton cycle, if so, we can get
one in polynomial time; if not, our algorithm fails in polynomial time, then we give the result
No.
An n vertices graph has up to (in fact less than) 9*n*(n-1)/2 different main segments. For each
main segment, we assign a key value to it. The initial key value is n. We put all the values in a main
segment key value matrix.
For convenience, we only prove this algorithm for un-directed graphs with degree 3, because this is
also an NP complete problem [21].
In the later proof process, for convenience of proof, because we suppose the graph has at least one
Hamilton cycle, we choose one Hamilton cycle as the main goal Hamilton cycle.
Please note: we use the concept main goal Hamilton cycle in order to explain the proof well.
We can choose any one Hamilton cycle of this graph as the main goal Hamilton cycle. We will
explain this clearly later. As this concept is only for the proof, in real computation, we do not know
which one is the main goal Hamilton cycle.
We call an edge which is contained in the main goal Hamilton cycle a good edge, otherwise, a bad
edge.
Suppose that aijkfebcdghla is the main goal Hamilton cycle and the (k, l)s one broad cycle be
abcdefghijk*la. We call the segment bcd a good part in this broad cycle, they are connected (do not
contain breaks) and all their edges are good edges (at its two end sides, de and ba are not good edges).
Also al, gh, ijk, fe are good parts. We call each good parts two end vertices (for example vertices b, d)
side vertices, and call other vertices inner vertices in this part. We also call vertices k, l break side
vertices as stated before.
If we change a broad cycles some vertices positions and keep the main segment, all break
segments and the number of breaks unchanged, we say that we re-permute this broad cycle.
When we do a useful cut and insert on broad cycle C1 to get a new broad cycle C 2 , if we
prescribe that after this cut and insert, all the inner vertices in C1 are still inner vertices in C 2 ( all
good edges in C1 are all still in C 2 ); at least one coming edge in C 2 is a good edge, and at least one
such new good edge is incident upon one vertex of C1 s core consecutive pair. We call such a useful cut
and insert a good useful cut and insert. If C 2 s main segments broad cycle with the same or less
number of break consecutive pairs already exists, we call this cut and insert a good cut and insert. We
always keep the main goal Hamilton cycle. Good edges, bad edges and a good cut and insert depend on
the main goal Hamilton cycle.
If we do a good cut and insert on a k breaks broad cycle to get a k+1 breaks broad cycle, it means
that we can do an extension on each break side vertex (a key vertex of the extension) o f the main
segment.
Note: when we compute on a graph, we do not know which one is a good cut and insert,
because we do not know the main goal Hamilton cycle and the good edges. This concept is only for
our proof.
We call such kind of main segment xy*uv y*us one useful main segment or a useful main segment,
if xy and uv are good edges. A break consecutive pair has four different useful main segments. Usually
after good cut and inserts, the new broad cycles main segment is a useful main segment.
In a broad cycle, we call two consecutive vertices ab a side vertex pair if ab is a good edge and at
least one of a, b is a side vertex. After a good useful cut and insert, a new main segment is constituted by
two side vertex pairs.
If we do a good cut and insert on broad cycle 1 to get a broad cycle 2, we say that the broad cycle 1
is the broad cycle 2s father or ancestor, and the broad cycle 2 is the broad cycle 1s son or descendant.
If we do good cut and inserts step by step on broad cycle L1 of main segment m1 to get a Hamilton
cycle, we call it L1 s (or m 1 s) final goal Hamilton cycle.
For a broad cycle, if we can do one or more good useful cut and inserts step by step on it to get a
Hamilton cycle, we call it a good useful broad cycle.
How to know a broad cycle is a good useful broad cycle and the good cut and insert? They depend
on the main goal Hamilton cycle, because whether an edge is a good edge or a bad edge depends the
main goal Hamilton cycle. But a broad cycles final goal Hamilton cycle may be different from the main
goal Hamilton cycle and two broad cycles final goal Hamilton cycles also may be different. These do
not have contradiction. We have two different cases:
Different case 1: in this case, only the inner vertices in one broad cycle change the ir positions in
another broad cycle and also this utterly does not affect the good cut and inserts. We take an example to
explain: suppose the main goal Hamilton is: abjihgfedclmnopa. A broad cycle is: abcdefghij*lmnopa,
ij*lm is its main segment. We do a rotation on it to get a Hamilton cycle: abjihgfedclmnopa, it is the
broad cycles goal Hamilton at this permutation. But we can re-permute the broad cycle as:
abcdhij*lmnefgopa, we do a good cut and insert ( the same one as on the former broad cycle) on it to get
another Hamilton cycle: ajihdclmnefgopa.
Different case 2: suppose that the broad cycle ajihefgdcbnopklmqa is the main goal Hamilton cycle,
abcdefghijklmnop*qa is a broad cycle of the main segment op*qa. After a good cut and insert we get:
abcdefghij*nopklmqa. Then we do another good cut and insert (a rotation) on it to get
ajihgfedcbnpopklmqa. This is the broad cycles final goal Hamilton cycle. Please note that the main goal
Hamilton cycle is different from the broad cycles final goal Hamilton cycle, but we define the good
edge, bad edge and good cut and insert still according to the main goal Hamilton cycle.
Please note: in real computation, because we do not know the main goal Hamilton cycle, we may
get a Hamilton cycle by a non-good useful cut and insert. This Hamilton cycle may be different from the
main goal Hamilton cycle, also different from the goal Hamilton cycles in the above two different cases.
The concept of main goal Hamilton cycle is important. Now we explain it carefully. 1) At first, we
can choose any one Hamilton cycle of this graph as the main goal Hamilton cycle. Later, when we
decide good edges, good cut and inserts, or good useful broad cycles, we always keep the same main
goal Hamilton cycle. 2) After we have got one or more good useful broad cycles, each good useful broad
cycle has its final goal Hamilton cycle. Different good useful broad cycles may have different final goal
Hamilton cycles. One main segments good useful broad cycles with different permutations may have
different final goal Hamilton cycles. Also a good useful broad cycles final goal Hamilton cycle may be
different from the main goal Hamilton cycle. For these, there are two different cases as stated above. But
for a broad cycle, we define the good edges, bad edges and good cut and insert always according to the
main goal Hamilton cycle. All these we can see in the process of our proof.
Apparently, if we can do good useful cut and inserts on L1 of main segment m 1 step by step (i.e. to
do one good useful cut and insert on L1 of main segment m1 to get a broad cycle L2 of new main segment
m2 , then do one good useful cut and insert on L2 of main segment m 2 to get L3 of main segment m3 , , if
there is no new main segment, we choose a new produced break segment as the current main segment to
continue), at last we can get such a broad cycle Lk in which the break in m1 and all the new produced
breaks (after L1 ) disappear. We call Lk the main segment m1 s final goal broad cycle. We call the breaks
in L1 but not in Lk (except the break in m1 ) in-scope breaks of m 1 , otherwise out-scope breaks of m1 .
If a broad cycle of a main segment with k (k>0) breaks already appeared, we call this main segment
with k or more breaks a used main segment, i.e., a broad cycle of this main segment with k or more
breaks cannot appear later. If a side vertex pair is contained in a used main segment, we call it a used
side vertex pair.
If we can do a good cut and insert on a broad cycle to get a new broad cycle with only one (or zero)
new break (please note that every cut and insert only produces at most two new breaks), we call it a easy
broad cycle, otherwise a hard broad cycle. Usually most broad cycles are easy broad cycles. Only at
special case, a broad cycle is a hard broad cycle. We take a n example to explain the special case of a
hard broad cycle: a hard broad cycle L1 is: abcdefghijklmnop*qrstuvwxa, other edges: ah, bw, cf, du, el,
gq, ip, jn, mt, os, pk, qx, rv. Please note that ip, qx, are good edges but ij, xw are also good edges. The
main goal Hamilton cycle is: abcduvwxqrstmnopijklefgha. So we cannot do a good cut and insert on it to
get a broad cycle with only one new break. We can cut the segment ijklmnop, do an extension on it and
then insert it between de, then we get a broad cycle L2 : abcd*mnopijklefgh*qrstuvwxa with two new
breaks (and thus seems two new main segments). We call the segment gh*qr a quasi- main segment, call
cd*mn an additional main segment and we choose the quasi- main segment as the new main segment.
Each broad cycle can have only one main segment. Suppose that L2 has k+1 breaks. The new main
segment cannot repeat with k+1 breaks (i.e., if such a main segment with k+1 or less breaks already
exists, this cut and insert is not a useful cut and insert.). The additional main segment may repeat or may
not repeat a former main segment with the same (or less) number of breaks. But we first have to try to
get one which does not repeat. And later, any new main segment of a k+1 breaks broad cycle cannot be
the same as the quasi- main segment and its descendants.
Please note that in real calculation, usually we do not know which is an easy or a hard broad cycle,
so we may do a useful cut and insert of kind 5 on an easy broad cycle, this does not matter. For an easy
broad cycle, if we do a useful cut and insert on it to get a new broad cycle with two new breaks, this
does not affect that we still can do a useful cut and insert on it to get a new broad cycle with one new
break later, because the former has more breaks. The main segment key value matrix is for this case.
Now, we describe the algorithm concisely as following:

Algorithm FindHCycle:

For an n vertices graph, firstly, we can easily construct a broad cycle L1 with r (r>0, if it is 0, this is
enough) breaks. We only guarantee that there are no isolated vertices in L1 . This requirement is easy to
get for a three degree graph. Later we must always keep the property of no isolated vertices in any
new-produced broad cycle. Also any other break segment cannot be destroyed unless the break disappear
as a gone break after a useful cut and insert. For each break, we have a possible main segment. We call
each one a seeded break segment and call its break a seeded break. Later, we do useful cut and inserts on
the broad cycle to get new broad cycles with new main segments and do useful cut and inserts on new
broad cycles to get more new broad cycles with new main segments. We call these new main segments
(also including quasi- main segments and additional main segments if they will be a s main segments later)
produced main segments and all new breaks produced breaks. We firstly choose any one of the
seeded main segments in L1 as the current new main segment (say m1 ). And then initialize the main
segment key value matrix (set each value to n).
After a useful cut and insert on L1 of m1 we get a new broad cycle with a new main segment (or if
there are no new breaks, we try to choose one break segment in this broad cycle as the new main
segment), the number of breaks of the new broad cycle must be less than this new main segments old
key value and we use the number of breaks to update this main segments key value in the main segment
key value matrix. Then we continue to do useful cut and inserts on L1 according to width- first. Because
usually there are more than one possible useful cut and inserts on the current main segment of the
current broad cycle, we use the width-first rule. In this width- first way, we can get a broad cycle tree.
We design a special queue and put each new broad cycle at the rear of the special queue. If we get a new
broad cycle, then we add the new broad cycle at the rear of the queue. And if an old broad cycle with the
same main segment of the new broad cycle but with more breaks already exists in the special queue,
delete the old one from the special queue. For the width- first search, each time we take a broad cycle
from the front of the queue, and do useful cut and inserts only on the current main segment (i.e., when
cut a segment we always cut from the break of the current main segment). If we take a broad cycle from
the queue on which we cannot do a useful cut and insert to get a new broad cycle, it is a leaf and we
delete it (still keep the main segment key value) and then take another broad cycle from the queue. Also
if a broad cycle is done (i.e., all possible new broad cycle s are got by useful cut and inserts from the
current main segment), we delete it (still keep the main segment key value, for any deleted main
segment). If after a useful cut and insert we get a new broad cycle with a new main segment, this new
main segment will be as a current main segment later when this broad cycle is took out from the queue.
If we get a new broad cycle with a quasi- main segment and an additional main segment, we choose the
quasi- main segment as the new main segment. When we do a useful cut and insert of kind 4 or kind 5,
for the additional main segment, we first try to choose such one which does not repeat a former good
main segment (choose this one whose old key value is the biggest) as stated before. If there is no new
break after a useful cut and insert (or after a useful cut and insert of kind 4), we will try to choose one
break segment in this broad cycle as the new main segment. We first try to choose a first kind of
additional main segment as the new main segment. If without such a main segment and there are some
second kind of additional main segments, this broad cycle die and we take it out from the queue (delete
it) and then take out another broad cycle. If there are no additional main segments, i.e., no produced
breaks, we choose a seeded break segment as the new main segment and initialize the main segment key
value matrix all to n. Then do the above process again (i.e. a new tree, except the current broad cycle,
delete all broad cycles in the special broad cycle queue before we begin this new tree). Until all the
seeded breaks and produced breaks disappear and thus we get a Hamilton cycle. Or, until at any time we
cannot continue to get a new broad cycle (until the special queue is empty), this means no Hamilton
cycle in the graph.

Please note that in this algorithm, for a main segment, we construct a broad cycle which
contains this main segment. Except the four vertices of the main segment, the positions of other
n-4 vertices are arbitrary. We do not need to gene rate all the permutations of the n vertices, but
only need to prove that at each big step we can have a useful cut and insert which can get a ne w
broad cycle until a Hamilton cycle is got. So, at first, each broad cycle may contain many breaks.
We only make these breaks become less and less by useful cut and inserts on the broad cycles of
the broad cycle set (updated continually).
Time Complexity: at each big step, for one broad cycle, when we cut a segment, try to insert it
between two consecutive vertices at any place of the rest part of this broad cycle, there are O(n) different
points to be inserted. For each broad cycle, there are O(1) key segments. The extension on the key
segment S needs O(n) time. After this, we need to compare to decide if the result is a main segments
new broad cycle which contains less break consecutive pairs than its old one. The comparison needs O(1)
time (by memory). There are O(n2 ) different main segments. Each main segment has O(n) key values
(from 0 to n). But because each time we do the algorithm for one seeded break segment, logically we
can get any one main segments broad cycle with O(1) more breaks. So, this value should be O(1). There
are O(n) seeded breaks. So, all the time complexity is O(1)* O(n2 )* O(n)*O(n)* O(1) *O(n)= O(n5 ).

IV. Proof
Next we will prove the above algorithm FindHCycle. Please note that the jobs in the following
lemmas are only for the proof, in practical computation for a big graph, we do not need to do these jobs.
Please note that for a one break broad cycle, if each ve rtex degree is 3, the opportunity to
re-permute a broad cycle is very limited. This is the foundation logic of the proof.

Lemma 1: 1) if there are no gone breaks (except the main break), after a good useful cut and insert
of kind 1, kind 2 or kind 3 (i.e., any of them) on each of two broad cycles with different useful main
segments, the two new main segments must be different. It also holds for two quasi- main segments of
good useful cut and inserts of kind 5 or one quasi- main segment of a good useful cut and inserts of kind
5 and a new main segment of a good useful cut and insert of kind 1, kind 2 or kind 3. 2) if there are no
gone breaks (except the main break), a new main segment of a good useful cut and insert of kind 1, kind
2 or kind 3 cannot be the same as an additional main segment of a good useful cut and insert of kind 5
(or kind 4). 3) if there are no gone breaks (except the main break), for a hard broad cycle L1 , after a good
useful cut and insert of kind 5, we get a new broad cycle L2 with an additional main segment a2 , then for
the descendants of L2 , after a2 was as a main segment to disappear, we cannot get such a hard broad
cycle, after a good useful cut and insert of kind 5 on which we get the same additional main segment as
a2 . This also holds for the additional main segment of kind 4. 4) a new main segment of a good useful
cut and insert of kind 1, kind 2 or kind 3 which has some gone breaks (besides the main break) cannot be
the same as an ancestor main segment of a good useful cut and insert of kind 1, kind 2 or kind 3 which
has no gone breaks (except the main break).
Proof:
Next, all our proof is on how to get a Hamilton cycle from a one break broad cycle. At last we show
that for a broad cycle with more than one break, we only need to do the algorithm repeatedly.
Now we suppose an algorithm as following:
Algorithm 1: From a main segment m 1 of a one break broad cycle L1 , we do a good cut and insert on
it. For a hard broad cycle, we do a good cut and insert of kind 5 and for an easy broad cycle, we do kind
1, kind 2 or kind 3. Recursively, if we get a hard new broad cycle, we do a good cut and insert of kind 5
on it and then choose the quasi- main segment as the new main segment and continue to do a good cut
and insert on the new broad cycle. If the new broad cycle is an easy broad cycle, we do kind 1, kind 2 or
kind 3 on it. Until we have a good cut and insert to get a new broad cycle with no new breaks or we have
a good cut and insert of kind 4 to get a new broad cycle with only one additional main segment. We call
this new broad cycle the first goal broad cycle of m1 . In the meantime, at each step, we can re-permute
each broad cycle before do a good cut and insert on it. When we re-permute it, keep each break segment
unchanged. We call each steps main segment a key descendant main segment of m 1 and call all the side
vertex pairs whose break side vertices are adjacent to break side vertices of these key main segments key
descendant side vertex pairs of m1 . In this way, we also have key descendant quasi-main segment and
key descendant additional main segment. Let m2 be one key descendant main segment of m1 . In the same
way, m2 has its key descendant main segments and key descendant side vertex pairs. And from m1 to m2 ,
the main segments are key ancestor main segments of m2 and the side vertex pairs are key ancestor side
vertex pairs of m2 . We call all the key descendant main segments of m1 including m1 the key main
segment set of m 1 and call all the key descendant side vertex pairs of m1 including m1 s the key side
vertex pair set of m1 . Then we choose a first kind of additional main segment in the new broad cycle as
new main segment to continue to do so to get new broad cycles with new main segments. The first kind
of additional main segment has its own key descendant main segments and a new key main segment set.
Then we continue. Until we get the final goal broad cycle of m 1 .We call all the main segments to get in
this way good main segments. For an additional main segment, only if it is as a main segment later, it is
a good main segment. This is a depth- first search.
Algorithm 2: the same as algorithm 1, only difference: at each step, we do not re-permute the broad
cycle.
Please note: the above two algorithms are only for the proof by supposition.
In the algorithm 1, from m1 to its final goal broad cycle, we have a good main segment set and a
sequence order of good main segments. For different permutations of each steps broad cycle, we may
have different good main segment sets and different sequence orders of good main segments. We want to
prove that in any such a sequence order of good main segments, a later good main segment cannot repeat
a former one and then we only concern the latest (lowest) descendant in the sequence order of good
main segments.
We always concern useful main segments, because except the first broad cycle, we always can
get useful main segments by good cut and inserts. We call the above each steps new main segment
a good main segment. And in this proof, we only concern good main segments. We want to prove
that from a main segment to its final goal broad cycle, all the good main segments do not repeat (a
main segment whose broad cycle contains more breaks can be repeated by the same main segment
whose broad cycle contains less breaks), in real calculation, when we do not know which one is a
good or bad cut and insert.
We prove the lemma 1 in this way: to take an example to explain, because for each item, we only
need to check several possible cases.
1) Considering the degree 3, we can easily get it.
2) We take an example to explain. A broad cycle is: abcd*efghijklmnopqrst we do a good cut
and insert of kind 5 on it to get: abcd*mnopijklefgh*qrst Please note that if we want to get a
new main segment of gh*qr by one or more good cut and inserts of kind 1, kind 2 or kind 3, gh
and qr must be side vertex pairs, i.e., at first the broad cycle must contain the segments ghij and
opqr, but if a broad cycle contains these two segments, we cannot get the new main segment
gh*qr by one or more good cut and inserts of kind 1, kind 2 or kind 3.
3) We take an example to explain. A broad cycle L1 is: yz*abcdefghijklmnopqrstuvwx. We do a
good cut and insert of kind 5 on it to get L2 : yz*ghidefabc*jklmnopqrstuvwx. Now we only
concern the additional main segment (we may suppose that the quasi- main segment is done).
We do a good cut and insert of kind 3 on it to get L3 : yz*ghidefabcmnojkl*pqrstuvwx. We do a
good cut and insert of kind 3 on it to get L4 : yz*ghidefabcmnojklstupqr*vwx. If we want to get
an additional main segment of bc*jk by a good cut and insert of kind 5, a broad cycle has to
contain these segments: bcde, hijk, if we re-permute L3 to let it contain these two segments, the
segment mno must produce a new break. For L4 , if it contains the above two segments, the
segments mno or stu must produce a new break. We can check all possible cases that no matter
how many good cut and inserts on L2 and then we re-permute the new broad cycle, it cannot
contains the above two segments with breaks unchanged. Please note that if a new broad cycle
contains an additional main segment of a1 : *mn, it may contain the above two segments,
but this time the break of bc*jk must be an in-scope break of the main segment a1 , so it can
repeat. On the other hand, because we do a width-first search, we get a new main segment in
 shortest way from the root. But in L4 , if we want it contains the two segments without new
breaks, we have to put the segment stu in other place, which lets many vertices change their
positions and many vertices recover to their old positions. This is not a shortest way, so it
cannot happen in a width- first search. We can check other possible cases in the same way.
4) We take an example to explain. A broad cycle L1 is: abcd*efghijklmnop*qrstuvwx. op*qr is the
main segment and cd*ef is a former additional main segment. dm, el, ax are bad edges and dq,
ex, hi are good edges. We do a good cut and insert on it to get L2 : abcdqrstuvwxefghijklmnop*.
The new main segment is op*ab. If this main segment repeats a former main segment, a former
broad cycle must be as this L3 : wxabklefop*mn, so we can do a good cut and insert on it
to get a broad cycle with the main segment of op*ab. But please note that by the property of a
good cut and insert, when being re-permuted in some way, the main segment op*qr can be as a
father of the main segment op*mn, so it cannot be a descendant of op*mn (by 1), 2), 3)). This is
a contradiction. On the other hand, if we re-permute L1 , we have to keep the break segments
unchanged, so we still cannot get a son as the broad cycle L3 . All other cases also have such
contradiction. Let us see another example: a broad cycle L1 is: zyxwvutsrqponmlk*abcdefgh*ij...
lk*ab is a seeded break segment, gh*ij is the main segment. After a good cut and insert we get
L2 : zyxwvutsrqpo*hgfedcbanmlkij... Then L3 : zyxw*rqpovutshgfedcbanmlkij... Then after
another good cut and insert L4 : z*wxyrqpovutshgfedcbanmlkij... Now we want to show that no
matter after how many good cut and inserts, if we get a hard broad cycle Lk , we cannot do a
good cut and insert of kind 5 on it to get the additional main segment po*hg. If we can, the
broad cycle must contain the two segments ponm, ghab. If we re-permute L3 and let it contain
the two segments, the vertex s must become a break side vertex. If we re-permute L4 and let it
contain the two segments, the vertex s or vertex y must become a break side vertex. If this break
is a break of an additional main segment, then the break of po*hg is an in-scope break of the
additional main segment, so po*hg can repeat. Also for the same reason as in 3), if the broad
cycle contains the two segments without new breaks, many vertices must recover to their old
place, but in width- first way, this cannot happen.
For all other possible cases we can prove in the same way as above.

Lemma 2: if a graph has at least one Hamilton cycle, at any time of the algorithm, we always have
a good useful broad cycle, until a Hamilton cycle is got. On the other hand, if the algorithm fails at any
time within O(n5 ), it means that there are no Hamilton cycles in the graph.

Proof:
Now from a one break broad cycle L1 , we do good useful cut and inserts. Firstly we try to do good
useful cut and inserts of kind 1, kind 2 or kind 3.
Suppose that from L1 we do some good useful cut and inserts of kind 1, kind 2 or kind 3 step by step.
At each step, we can re-permute the broad cycle. Several steps later, we get a hard broad cycle L2 with
main segment m 2 . We do a good useful cut and insert of kind 5 on L2 to get L3 with a quasi- main
segment m31 and an additional main segment m32 . We choose m 31 as the new main segment and do good
useful cut and inserts of kind 1, kind 2 or kind 3 on it step by step. Several steps later, we get another
hard broad cycle L4 . We do a good useful cut and insert on L4 to get a new broad L5 with a quasi- main
segment m51 and an additional main segment m52 . Then we choose m51 as the new main segment and
continue to do good useful cut and inserts of kind 1, kind 2 or kind 3 on it. Suppose that several steps
later, we get a new broad cycle with no new breaks, then recursively, we choose one of the former first
kind of additional main segments as the new main segment and continue to do good useful cut and
inserts on it step by step. This is a depth- first way. At each step, we can re-permute the broad cycle.
Please note that we do this only for the convenience of proof and in real calculation we cannot know
how to do a good useful cut and insert.
Because in real calculation, we do not know which one is a good cut and insert, we have to prove
that no matter how to re-permute a good main segments broad cycle with the same number of breaks
and with all the break segments unchanged, the correctness of the algorithm still holds. This means that
no matter the useful cut and inserts are good useful cut and insets or non-good useful cut and
inserts in real calculation, the algorithm still works.
Now we consider the above broad cycle with break segments m 51 , m52 and m32 . For more breaks, we
can recursively think it in this way.
m2 , m31 , m4 , m51 are in the same key main segment set of m1 and are key descendant main segments
of m 1 .
By the 1) of lemma 1, the m2 cannot be the same as any key ancestor main segment of m1 . And also
the m31 cannot be the same as any key ancestor main segment of m 2 . For the m 32 , by the 2) of lemma 1,
m32 cannot be the same as one key ancestor main segment or any one ancestor good main segment.
If breaks of m 32 and m 52 are out-scope breaks of m31 , we do good cut and inserts on m31 step by step,
each new main segment cannot be the same as the key ancestor main segments of m2. Later, we choose
m32 (or m 52 ) as the new main segment, if the break of m52 is a out-scope break of m 32 , when we do good
cut and inserts of kind 1, kind 2 or kind 3 on m 32 , by the 1) of lemma 1, the new main segment still
cannot be the same as key ancestor main segments of m2 .
We do good cut and inserts of kind 1, kind 2 or kind 3 on m31 step by step to get a new broad cycle
L6 with new main segment m6 after several steps. Suppose the break of m32 or m52 is an in-scope break of
m6 , one break side vertex of them must be adjacent to one break side vertex of m 6 . By the 4) of lemma 1,
the new main segment cannot be the same as any key ancestor main segment of m6 .
After we get a new broad cycle with no new break, if we choose m32 as the main segment, and
suppose that the break of m52 is an out-scope break of m32 , after we finished m32 (got its final goal broad
cycle), we choose m52 as the main segment and do good cut and inserts step by step. If we get a hard
broad cycle and do a good cut and insert on it, by the 3) of lemma 1, the additional main segment cannot
be the same as m 32 .
Please note that we use the words good cut and insert, but in real calculation we do not know
which one is a good cut and insert, why? Because: 1) in real calculation, we do the algorithm in
width- first search, if the good son of a good main segment did not appear, we always have the
opportunity to get it; 2) we prove that when we re-permute each broad cycle, the lemma still holds.
In a word, by the lemma 1, from any one good main segment to its final goal broad cycle, all the
later good main segments do not repeat any former good main segments.
There are two kinds of additional main segments. The first: the main segments and all its descendant
main segments cannot be the same as former main segments. The second: they can be the same. If the
break of an additional main segment can be as an in-scope break of another main segment, it and its
descendant main segments can be the same as former main segments. If not, they cannot be. For the first
kind, we can prove they do not be the same as former main segments by lemma 1.
Now, we explain how to get the correct m31 and m32 from the m 2 . We surely can get the correct m31 if
it does not appear before, because it is the only one and consider the degree 3 and the width- first search.
But because we do not know good edges or bad edges, we cannot guarantee to get the correct m32 . Please
note that if only the cut and insert is a good cut and insert, then m32 is correct. If it is wrong, because we
first try to get a non-repeating one, later when it as the main segment, we can easily get the correct m32
only by one step of useful cut and insert. Please note that we always keep a break segment unchanged
unless the break disappear as a gone break after a useful cut and insert.
We only proved that a good main segment does not repeat any one of its ancestor good main
segments. But can it repeat a good main segment which is another descendant of its one ancestor? Now
we explain that if we get m6 in another way together with two other additional main segments mx and my
which are different from the m32 and m52 . Because m6 is a quasi- main segment, we still can prove that it
and its key descendant main segments cannot be the same as any former main segments. For the mx and
my , if they are got by good cut and inserts, we still can prove them in the above way. If they are not got
by good cut and inserts, as stated above, for each of them we can get a correct one by one step of good
cut and insert later. If a descendant good main segment of mx already exists in another broad cycle with
two breaks, it can be used as the current main segment. If we get a quasi- main segment m7 and there are
two other additional main segments m 71 and m72 in this broad cycle. Suppose the above m52 s break is a
out-scope break of m32 and m71 is a good descendant of m32 and m 52 is a good descendant of m72 . This is
a dead lock. The dead lock cannot happen due to the three reasons: 1) after m71 , the number of breaks for
m72 becomes less; 2) the order of width-first; 3) a good main segment cannot repeat its ancestor; 4) after
we get a main segments final goal broad cycle, the number of breaks minus one. Anyway, because of
these reasons, a broad cycle whose main segment is the lowest descendant good main segment (with the
same or less number of breaks) always can be a good useful broad cycle and there is no dead lock.
In the process of the proof, we only concern good main segments, but please note that in real
calculation, we do not know good edges or bad edges. Because we do the width-first search, for an easy
broad cycles son main segment (by a useful cut and insert of kind 1, kind 2 or kind 3) and for a hard
broad cycles son quasi- main segment, we always can get them, no matter at any place of the broad
cycle tree, i.e. if we get the father we always can get the son. But for the additional main segments, the
case is harder. So we have to prove that no matter how to re-permute the broad cycles with good main
segments, we can get the correct result. The proof is just in this way.
Now, for a one break broad cycle, we have three algorithms: algorithm 1, algorithm 2 and the real
algorithm FindHCycle. In real calculation, at each step, we do a useful cut and insert of kind 1 to kind 5.
We do not know if it is a good cut and insert, in width-first way.
Apparently, algorithm 2 surely can get a correct result. Because we proved that in the algorithm 1, all
the good main segments do not repeat, algorithm 1 also can get a correct result. In algorithm 1, we
re-permute any broad cycle, we do the width- first search in algorithm FindHCycle, and we always
concern the latest (lowest) descendant of good main segments in algorithm 1, so algorithm
FindHCycle also can get a correct result.
The above is the algorithm and proof for a one break broad cycle. If at first we get a broad cycle with
r (r>1) breaks (without isolated vertices), we call each break a seeded break, each break segment a
seeded segment. Firstly we choose any one seeded break segment as the main segment and do the
algorithm until we get its final goal broad cycle. In the meantime, if one other seeded break disappears,
because each seeded breaks two side vertex pairs are un- used and by the proof of lemma 1, it does not
affect the lemma 1, so it does not affect the algorithm. For the seeded break segments which still
unchanged, we choose one as the new main segment and update the main segment key value matrix,
initialize each value to n, delete all other broad cycles from the special broad cycle queue, and then do
the algorithm again.
So at any time we have a good useful broad cycle until a Hamilton cycle is got if it contains and if
the algorithm fails at any time it means that there is no Hamilton cycle in the graph.
So, we have proved that the lemma 2 holds for any graphs with degree 3.
By the lemma 2, because we always can have a useful cut and insert to get a new broad cycle, at
last, we can get a Hamilton cycle.
 So we have proved that for any graph whose vertex degree is three with any vertices, we always can
get a Hamilton cycle if it contains in polynomial time. We have the next theorem:

Theorem 1: the above algorithm FindHCycle can solve the Hamilton cycle problem in polynomial
time for any undirected graphs with vertex degree of 3. As this is an NPC, we conclude that: NP P .

V. Experiment Data
The above is only for the proof. This algorithm works very well for all kinds of undirected graphs.
A program on this algorithm has been tested over a hundred million times for graphs whose vertex
number is from 100 to 10000, also, these are sparse graphs, randomly produced, no failures. More
precisely, a random graph G = (V, E) in this problem is defined by n vertices and the following set of
edges: (i) The n edges forming a specific Hamilton cycle. We randomly produce these n edges in the
way like to shuffle a pack of n cards. (ii) The edges obtained by choosing each pair of distinct vertices {i,
j} V to be an edge with probability p, independently for all pairs. We control the graphs by changing
the p and different pairs may be with different p.
The data is shown as Table 1 (computer: HP PC, CPU: Intel 1G, Memory:1G):
T able 1 V is the number of vertices, N is the number of different inputs, Rs is success rate, t avg is average
run time of the program, t max is the run time of the worst case of the inputs. Run time is in seconds.
|V| N Rs tavg tmax
102 10 8
100% 0.0014 0.01
103 107 100% 0.07 0.1
104 104 100% 48 192

Also, we get the test data from the famous web site, the famous standard test bed on
http://comopt.ifi.uni- heidelberg.de/software/TSPLIB95/. On this web, there are 9 files for Hamilton
cycles. The program of our algorithm can calculate all the 9 files, very easy, very fast. The calculating
time for each is just like the time in the above table 1. For each file, we can quickly get a Hamilton cycle
which is different from the web owners, because each graph has more than one Hamilton cycle.

VI. Remarks

The P versus NP is a great problem. This paper is a hard job and now we give some remarks on it.
For one main segment, we construct a broad cycle which contains this main segment. Except the
four vertices of the main segment, the positions of other n-4 vertices are arbitrary. We do not need to get
all the permutations of the n vertices, but only need to prove that at each big step we can get a useful cut
and insert to make a main segments breaks become less until a Hamilton cycle is got. So, at first, each
broad cycle may contain many breaks. We only let these breaks become less and less by useful cut and
inserts on the broad cycles of the broad cycle tree (updated continually). But why do we need the four
vertices of a main segment? Because when we keep a main segment, we can get the lemma 1 and the
lemma 2.
How to understand this proof? First to understand a useful cut and insert: after such a cut and insert
we can get a main segments new broad cycle which contains this main segment and has less number of
breaks than this main segments old broad cycle or there is no broad cycle of this main segment before.
Also to understand clearly the main goal Hamilton cycle and why we can choose any one Hamilton
cycle as the main goal Hamilton cycle and then always keep it, see the explanation for it above.
 Thoroughly understand the useful cut and inserts of kind 1 to kind 5. Understand their properties
and that why they are enough for the algorithm.
Please note that for a one break broad cycle, if the vertex degree is 3, the opportunity to re-permute
a broad cycle is limited (when keep the main segment and all other break segments unchanged). This is
the foundation logic of lemma1 and lemma 2.
Lemma 1 is the core and the foundation of the proof. The key is to understand that the main
segments do not repeat as stated above. It is everything and all of the proof. It is hard to understand.
We have to understand the main segment of 4 consecutive vertices; to understand the degree 3; to
understand the in-scope breaks and the out-scope breaks. The most important core is: to understand that
in the proof we only concern the good cut and inserts and the good main segments by re-permuting
broad cycles with good main segments and to understand the good main segment set and the sequence
order of good main segments in algorithm 1 and why they are important in real calculation; to
understand the lemma 1.
The logic is very easy. If we always can do good useful cut and inserts (as algorithm 2), surely we
can get a correct result. Because in real calculation we do not know good edges or bad edges, we cannot
do so. But because we do the width- first search, if we have a father, we always can get the son, no
matter at what place of the broad cycle tree, though may with different permutation. So we only have to
prove that no matter how to permute the broad cycles, a descendant good main segment does not repeat
an ancestor of it and there are no dead locks.

REFERENCES

[1] S.A.Cook, The complexity of theorem proving procedures, Proceedings of Third Annual ACM Symposium, on
Theory of Computing, Association for Computing Machinery, New York, 1971,151-158
[2] R.M.Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, R.E.Miller and
J.W.Thatcher,eds.,Plenum Press, New York, 1972, 85-104
[3] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc., 2(1952) 69-81
[4] O. Ore., Note on Hamiltonian Circuits, Amer. Math. Monthly, 67(1960), 55
[5] G. H. Fan, New Sufficient Conditions for Cycles in Graphs, J. Combin. Theory, Ser. B, 37(1984), 221-227
[6] J. Christophides, Graph Theory, An Algorithmic Approach, Academic Press, New York, 1975
[7] P. Erdos and A. Renyi, On the evolution of random graphs, Bull. Inst. Statist. Tokyo38 (1961), 343-347.
[8] L. Posa, Hamiltonian circuits in random graphs, Discrete Math. 14(1976), 359-364
[9] J. Komlos and E. Szemeredi, Limit distributions for the existence of Hamilton circuits in a random graph, Discrete
Mathematics 43 (1983), 55-63.
[10] M. Krivelevich, E. Lubetzky, and B. Sudakov, "Hamiltonicity thresholds in Achlioptas processes", presented
at Random Struct. Algorithms, 2010, 1-24.
[11] William Kocay, Pak-Ching Li, An Algorithm for Finding a Long Path in a Graph, Utilitas Mathematica 45(1994),
169-185
[12] Christos H. Papadimitriou. Computational Complexity. New York: Addison Wesley Publishing Company,1994.
[13] Sara Baase etc. Computer Algorithms: Introduction to Design and Analys is. New York: Addison Wesley
Publishing Company2000.
[14] R.Diestel,Graph Theory,Springer, New York, 2000
[15] M.R.Garey,D.S.Johnson,Computers and Intractability:A Guid to the Theory of NP-Completeness,Freeman,San
Francisco,1979
[16] L.Lovasz,Combinatorial problems and exercises, Noth-Holland, Amsterdam , 1979
[17] Yuri Gurevich and Saharon Shelah Expected computation time for Hamiltonian Path Problem SIAM J. on
Computing 16:3(1987) 486502
[18] Yuri Gurevich,Complete and Incomplete Randomized NP Problems 28th Annual Symposium on Foundations of
Computer Science, (1987), 111-117.
[19] D.Johnson,The NP-completeness column-an ongoing guid,Journal of Algorithms 5,( 1984), .284-299
[20] William Kocay, Groups & Graphs, a MacIntosh application for graph theory, Journal of Combinatorial
Mathematics and Combinatorial Computing 3 (1988), 195-206.
[21] M.R. GAREY etc. The planar Hamiltonian Circuit problem is NP-Complete. SIAM J. COMPUT. Vol5, No. 4,
1976