SOME GRAPHIC USES OF AN EVEN NUMBER OF ODD NODES

In memory of Francois Jaeger

Kathie Cameron <kcameron@mach1.wlu.ca>
Department of Mathematics
Wilfrid Laurier University
Waterloo, Ontario, Canada N2L 3C5

Jack Edmonds <jedmonds@math.uwaterloo.ca>

Abstract: Vertex-degree parity in large implicit "exchange graphs" implies
some EP theorems asserting the existence of a second object without
evidently providing a polytime algorithm for finding a second object.

Subject classification codes: 05C45, 05C38, 05C05, 68R10, 68Q25

Keywords: parity, hamiltonian, exchange graph, path, tree, flower,
lollipop, circuit, existentially polytime

Footnote: Research supported by the Natural Sciences and Engineering
Research Council of Canada and the Danish Natural Science Research Council.
Partly included in a course called "Existential Polytime" presented at
Odense University with Bjarne Toft.

Perhaps the simplest useful theorem of graph theory is that every
graph X has an even number of odd (degree) nodes. We give new proofs of
several theorems each of which asserts that, for any input G satisfying
specified conditions, G has an even (or odd) number of H's satisfying
specified conditions. Each proof consists of describing an "exchange
graph" X, quite large compared to G, such that the odd nodes of X are the
objects H which we want to show there is an even number of (or such that
all but an odd number of the odd nodes of X are the objects which we want
to show there is an odd number of).
Each of these theorems is not so easy to prove without seeing the
exchange graph. They include as corollaries, in Section 5, the results of
Andrew Thomason [1] proving the 1965 conjecture of Lin [cf.6,7,8] that the
union of any two edge-disjoint hamiltonian circuits of any graph G is also
the union of two other edge-disjoint hamiltonian circuits of G (and hence
two edge-disjoint hamiltonian circuits of G can not be neighbour vertices
in the convex hull of the hamiltonian circuits of G, [6]). They include,
in Section 6, Berman's generalization [4] of Thomason's generalization [1]
of the famous Smith theorem, that each edge in a cubic graph G is in an
even number of hamiltonian circuits of G, which seems to have taken many
inspections and years to reach the transparency of Section 6. Using the
exchange graphs, the theorems seem suitable for the first hour of an
introduction to graph theory.
We are thus led to the speculation of what other of the many beautiful
theorems asserting that there is an even number of something, or an odd
number of something, have associated exchange graphs. One of our favorites
for hoping that there is an associated exchange graph is the ancient, but
not yet easy to prove, theorem of Redei which says that every tournament
has an odd number of directed hamiltonian paths.
Our simplest of useful theorems is so simple that any exchange-graph
proof can in principle be replaced by an almost-as-simple counting argument
which doesn't mention an exchange graph. However having an exchange graph
X, besides imposing special structure on the counting, and making matters
transparent, opens graph theoretic questions about X -- like how great can
be the shortest distance from one odd vertex to another in X.

1. Theorem 1 [Toida,2]. For any graph G such that the degree of every
node is even, each edge e of G is in an odd number of circuits of G. (This
is immediately equivalent to the fact that every two nodes of G are the
end-nodes of an even number of paths in G.)

An exchange graph X for Theorem 1: Choose a node r of edge e. The
odd-degree vertices of X are the edge e by itself and the circuits
containing e. The even-degree vertices of X are the (simple) paths of G,
of length > 1, which begin with node r and edge e. Two vertices of X are
joined in X if one can be obtained from the other by adding (or by
deleting) an edge of G, or if they are the two maximal paths, rooted at r
and edge e, of a lollipop (not necessarily spanning) whose stick is rooted
at node r and edge e. A lollipop is a graph consisting of a circuit and a
path which intersect in a single node. The path is called the stick.

The lollipops which span a graph G, and which are rooted at a node r
and edge e, were introduced in [1] to be the edges of a simpler exchange
graph than the one above, which Thomason calls "the lollipop graph". Its
vertices are the hamiltonian paths of G which are rooted at node r and edge
e. Its odd vertices are the ones which end at odd nodes of G and extend to
hamiltonian circuits of G, or which end at even nodes of G and don't extend
to hamiltonian circuits of G. It proves the following generalization of
Smith's theorem:

Theorem 0 [Thomason,1] For any graph G such that the degree of every
node is odd, except possibly the end-nodes of edge e in G, e is in an even
number of hamiltonian circuits H+e of G.

By deleting one of the end-nodes r of edge e in Theorem 0, and thus
deleting all edges incident to r, and leaving the end-node r' of edge e, we
are left with a graph G' such that the hamiltonian circuits containing e in
G correspond to the hamiltonian paths of G' which start at r' and end at an
even node of G'. Thus Theorem 0 is immediately equivalent to
Theorem 0'. For any node r' in any graph G', there is an even number
of hamiltonian paths from r' to an even node of G'

Each of our exchange-graph proofs consists simply of confirming that
the vertices described as odd in the exchange graph X are indeed joined in
X to an odd number of other vertices of X, and that the vertices described
as even in X are indeed joined in X to an even number of other vertices of
X. For no important reason we use the word "vertex" for a node of the
exchange graph, and the word "node" for a node of the graph G of the
theorem. After seeing the exchange graphs, it may be easier to finish the
proofs oneself than to read what we are calling "proofs".

Proof of Theorem 1. From the edge e, joining node r to say node u in G (of
Theorem 1), we can reach other vertices of exchange graph X by adding any
edge meeting u which is different from e. So the degree of vertex e in X
is one less than the degree of node u in G -- that is, odd.
Consider a circuit C of G containing e. Let e' be the other edge of C
meeting r. From vertex C of X we can reach another vertex of X only by
deleting e' from C. So the degree of vertex C of X is 1 -- that is, odd.
Consider a path P in G of length > 1, beginning with r and e, and
ending with, say, node z. The degree of vertex P in X equals the degree of
node z in G, because for each edge zv joining node z to a node v in G: if
zv is in P, we can delete zv to get a shorter path; if v is not in P we can
add zv to get a longer path; and if v is in P but zv isn't, then P together
with zv is either a circuit of G containing e (if v=r), or a lollipop whose
stick is rooted at r and e. In the latter event the two maximal paths
beginning at r of the lollipop are P and the path P' consisting of the
lollipop minus the edge which follows v on the other side of r in P (that
is, P' is P from r to v, then vz, then P backwards from z.) So the degree
of vertex P in X is even like the degree of node z in G. End of proof of
Theorem 1.

Before moving on to some other exchange graphs, up front here is
perhaps the best place to describe a consequence of Andrew Thomason's
seminal Theorem 0 which we first discovered and presented in early 1996
while we were working at three great universities in Denmark: University of
Copenhagen, Odense University, and the Technical University of Denmark:

Corollary 0.1. Let G be a graph and H a hamiltonian circuit in G.
Let R be one of the connected components of G - E(H). If each connected
component of G - E(H), except perhaps R, has an even number of nodes, then
for every edge e of H which hits a node, say r, of R, there is a subgraph
G(e) of G, containing H, such that e is in a positive even number of
hamiltonian circuits of G(e). In particular, G contains another
hamiltonian circuit containing e. In particular, where G is a graph with a
hamiltonian circuit H such that G - E(H) is connected, every edge of H is
contained in another hamiltonian circuit.

Proof. For each component K of G - E(H), if K has an even number of even
(degree) nodes, arbitrarily name them u(1), v(1), u(2), v(2), ..., u(m),
v(m). If K is R and has an odd number of even nodes which does not include
node r, then arbitrarily give the names, say u(1), v(1), u(2), v(2),
...,u(m), v(m), to all the even nodes of K and node r. If K is R and has
an odd number of even nodes which does include the node r, then give names,
say u(1), v(1), u(2), v(2), ..., u(m), to all the even nodes of K except
node r.
For each component K of G - E(H), let P(i) be a path in K between u(i)
and v(i). Let F(K) be the set of edges which are in an odd number of the
paths P(i), i=1,2,...,m. Each node, u(1), v(1), u(2), v(2), ..., u(m),
v(m), of K hits an odd number of edges of F(K). Every other node of K hits
an even number of edges of F(K). [G minus the edges F(K) for all K] is a
subgraph G(e) of G, containing H, such that the degree of each node in
G(e), except possibly node r, is odd. Apply Theorem 0 to G(e). End of
proof.

There are still more general conditions on G - E(H), where H is a
hamiltonian circuit in a graph G, which imply that there is another
hamiltonian circuit (for example where there are at most two components R
of G - E(H) which have an odd number nodes, and there is an edge e of H
which has a node in each R) but that is not the point of the present paper,
which is that there is a variety of beautiful exchange graphs, including
the lollipop graph, which prove the existence of second objects without
there evidently being a good algorithm for finding one. To our
consternation and amazement, we have not been able to find any polytime
algorithm for finding a second hamiltonian circuit whenever G - E(H) is
connected.
Andrew Thomason [1] proposes tracing the unique path from the given
1-degree vertex, H, to another 1-degree vertex in the lollipop graph, as an
algorithm for, given a cubic (3-degree) G, an H, and an e, finding another
hamiltonian circuit containing e. If in the more general, not necessarily
cubic, version of Theorem 0, the lengths of paths from one odd vertex H to
some other odd vertex in the lollipop graph were well-bounded relative to
the size of G, then perhaps some algorithm for finding such a path,
together with the algorithmically polytime proof of Corollary 0.1 from
Theorem 0, would provide a good algorithm for finding a second hamiltonian
circuit when G - E(H) is connected.
However, Cameron has found a rather complicated proof [5], for a
sequence of cubic graphs G proposed long ago by Adam Krawczyk, that the
length of the path between a pair of 1-degree vertices in Thomason's
lollipop graph (for Smith's theorem) grows exponentially with the size of
G.
In Sections 5 and 6 we describe some exchange graphs more general and
versatile than the lollipop graphs which could still conceivably provide
polytime algorithms. At least we have not yet shown that they do not, and
at least they seem to work well in practice.

2. Theorem 2 [Bondy and Halberstam,3]. For any graph G such that the
degree of each node is even, and for any positive integer k, each node r of
G is the beginning of an even number of length k paths in G.

In the case where k is one less than the number of nodes of G, Theorem
2 becomes:
For any graph G such that the degree of each node is even, each node r of G
is the beginning of an even number of hamiltonian paths in G. This is also
a special case of Theorem 0'. However we have not been able to find an
exchange graph which proves both Theorem 2 and Theorem 0', nor have we
found a way to prove one of these theorems from the other.

The exchange graph X for Theorem 2 is not very different from the
exchange graph for Theorem 1: The odd-degree vertices of X are the length
k paths in G beginning at node r. The even-degree vertices of X are the
paths in G beginning at r and having length from 0 to k-1. Two vertices of
X are joined in X if one can be obtained from the other by adding (or by
deleting) an edge of G; or if they are the two maximal paths beginning at r
in a lollipop rooted at r, or in a circuit containing r, with at most k
edges (it follows that these two paths have length at most k-1).

Proof. Consider a path P of length k beginning at r. The only way to
reach, by an edge in X from vertex P of X, a path of length at most k
beginning at r is to delete the last edge of P. So the degree of P in X is
1.
Consider a path P beginning at r of length from 0 to k-1. Let z be the
last vertex of P. The degree of P in X equals the degree of z in G,
because for each edge zv of G: if edge zv is in P, we can delete zv to get
a shorter path; if v is not in P we can add zv to P to get a longer path;
and if v is in P but zv isn't, P together with zv is a lollipop or a
circuit, with at most k edges, rooted at r, P is one of its maximal paths
beginning at r, and the other is P', the lollipop or circuit minus the
edge of P following v. Thus degree of vertex P in X is even since the
degree of node z in G is even. End of proof of Theorem 2.

3. Theorem 3 [Bondy and Halberstam,3]. For any graph G and node r of G,
such that the degree of each node is odd, and for any integer k>1, node r
of G is the beginning of an even number of length k paths in G. (The
differences between Theorem 2 and Theorem 3 are in replacing "each node is
even" by &quot;each node is odd", and replacing k>0 by k>1.)

Our proofs of Theorem 2 and Theorem 3 are interestingly different from
each other, though they are given as corollaries of the same unified
proposition by Bondy and Halberstam. Their proofs are beautifully simple
counting arguments which are worth comparing with the approaches here.
We strengthen Theorem 3 to:
Theorem 3'. For any graph G and node r of G, such that the degree of
each node is odd, except possibly for r which may be even or odd, and for
any integer k>1, each subset W of k nodes of G, including node r, is in an
even number of length k paths P in G such that r is the beginning node of P
and the other nodes of W are the interior nodes of P.

This follows from Theorem 0, where in the G of Theorem 0 multiple edges
between a node pair are allowed, by pasting together all the nodes not in W
to be a single node r', and joining r' to node r by a new edge e. Then the
paths P of Theorem 3' correspond exactly to the hamiltonian circuits
containing e, and Theorem 0 says that the number of these is even. The only
glich to this argument is that in describing exchange graphs, in particular
the lollipop graph which proves Theorem 0, we have assumed for simplicity
that the graph G is simple, i.e., no loops and no multiple edges between a
pair of nodes, whereas the pasting creates loops and multiple edges meeting
node r'. The truth and proof of Theorem 0 is preserved, where the G can
have multiple edges, by refining the description of the associated lollipop
graph. And thus we can say that Theorem 3', and hence Theorem 3, follows
from the multigraph reading of Theorem 0. However Theorem 0, as well as
Theorem 3, follows immediately from Theorem 3'.
And it is simpler, than describing the refinement of the lollipop
graph for proving the multigraph version of Theorem 0, to simply describe:

An exchange graph X for Theorem 3'. The even vertices of X are the paths
P' of length k-1 in G such that P' begins with node r and such that the
node set of P' is exactly W. The odd vertices of X are the paths P as
described in Theorem 3'. That is each such path P in G is a path P' plus
one more edge. The degree of each such vertex P in X is one. P is joined
in X only to the vertex P' obtained from P by deleting the final edge and
node of P. An even vertex P' of X is met by one edge of X for each edge of
G which is not in path P' and meets the final node of P'. If an edge of X
which meets a even vertex P' does not join P' to an odd vertex P, then it
is a lollipop rooted at r or a circuit containing r, with k edges, which
joins P' to another even vertex.

4. Theorem 4. For any graph G and a specified pair of odd numbers
(h(v),k(v)) for each node v of G, such that h(v)+k(v) is the degree of v in
G, there is an even number of subgraphs H which have degrees h(v) at the
nodes v of G.
(Multiple edges between two nodes are allowed.)

An exchange graph X for Theorem 4. Choose any node w of G to be a fixed
special node. Each vertex of X is a subgraph H (each using all nodes of
G). The odd vertices of X are H's having degrees h(v); that is, the
h-factors of G. The even vertices of X are H's in which node w has degree
h(w)-1, some one other node u has degree h(u)+1, and every other node v has
degree h(v). Two vertices of X are joined in X when each can be obtained
from the other by the H and its complement K in G trading single edges,
that is, by removing one edge from H and adjoining some other edge to H.

Proof. Consider an h-factor H, and K, the complement of H in G, which is a
k-factor. There is an odd number of ways to move to K some edge of H
hitting w, say edge e1. Then, where x is the other node hit by edge e1,
there is an odd number of ways to move to H some edge of K hitting node x
which is different from e1, say e2. Thus there is an odd number of ways to
choose e1 and then e2. Where u is the other node hit by edge e2, if u is
different from w then the resulting H is as described above as an "even"
vertex of X, and if u=w then the resulting H is another "odd vertex" of X.
There is no other way to obtain a vertex of X from an "odd vertex" H of X
by having H and K trade single edges. Hence the degree of each "odd
vertex" of X is odd. Similarly the degree of each "even vertex" of X is
even.

5. Theorem 5 [Berman,4]. For any graph G and a specified pair of numbers
(h(v),k(v)) for each node v of G, such that h(v)+k(v) is the degree of v in
G, there is an even number of partitions of the edges of G into a spanning
tree H which has degrees h(v) at nodes v and a spanning tree K which has
degrees k(v) at nodes v.
("Partition into H and K" means that the blocks H and K of the
partition are "ordered" or "labeled". When H1=K2 and H2=K1, the partition
into H1 and K1 is still different from the partition into H2 and K2. Hence
Theorem 5 is trivial when h(v)=k(v) for each node v.)

An exchange graph X for Theorem 5. Choose any node w of G such that h(w)=1
to be a fixed special node. Each vertex of X is a pair of subgraphs H and
K (each using all nodes of G) which partition the edges of G into two sets
each of size one less than the number of nodes of G. The odd vertices of X
are (H, K) such that H is a spanning tree of G having degrees h(v) and K is
a spanning tree of G having degrees k(v).
The even vertices of X are (H, K) such that K is a spanning tree of G
in which node w has degree k(w)+1, some other node u has degree k(u)-1, and
every other node v has degree k(v); in H node w has degree 0 (=h(w)-1),
node u has degree h(u)+1, and all other nodes v have degree h(v), and u is
in the unique circuit of H.
Two nodes of X are joined by an edge in X if each can be obtained from
the other by the H and K trading single edges.

Proof. Consider an (H, K) which is called an "odd vertex" of X, i.e.,where
H is an h-degree spanning tree of G and K is a k-degree spanning tree of G.
The only way to get another vertex which is joined in X to vertex (H, K)
is to move from H to K the one edge, say e1, of H which hits node w. This
creates in K a circuit with two "surplus" nodes, w and x. To get another
vertex of X, the unique edge e2 of the circuit which is different from e1,
and which meets node x, must then be moved from K to H, which creates a
unique cycle in H. Where u is the node different from x which is hit by
e2, u now has degree k(u)-1 in K, degree h(u)+1 in H, and is in the unique
circuit of H. That is we do have what we call an "even vertex". Hence the
degree of any "odd vertex" of X is 1.
Now consider an (H, K) which is called an "even vertex" of X. The
only way to get another vertex which is joined to it in X is to move to K
one of the two edges in the unique circuit of H which hit surplus node u of
H. Suppose we move one of them, say uz. This creates a circuit in K. The
degree of u in K is now k(u), and the degree of z in K is now k(z)+1. To
get the new vertex we must move, from K to H, the edge e2 of this cycle
which meets z and which is different from uz. If e2 hits w, we get a new
(H,K) where H is an h-degree spanning tree and K is a k-degree spanning
tree, an "odd vertex" of X. If e2 does not meet w, we get another "even
vertex." Thus the degree of every "even vertex" in X is 2. End of proof
of Theorem 5.

In each of the following four corollaries, G' is any 4-regular
(4-degree) graph. (The corollaries are of course vacuously true for other
graphs G'.) These corollaries were proved by Andrew Thomason [1], without
exchange graphs, by induction on the size of graph G'.

Corollary 5.1. For any two edges e1 and e2 of G', the edges of G' can
be partitioned an even number of ways into two hamiltonian circuits, one
containing e1, the other containing e2.
Corollary 5.2. For any node v of G', and for each of the three ways
to partition the four edges which hit v into two pairs, {av,bv}and {cv,dv},
the edges of G' can be partitioned an even number of ways into two
hamiltonian circuits, one containing edges av and bv, the other containing
edges cv and dv.
Corollary 5.3. The edges of G' can be partitioned an even number of
ways into two hamiltonian circuits.
Corollary 5.4. For any two edges e1 and e2 of G', the edges of G' can
be partitioned an even number of ways into two hamiltonian circuits, one of
which contains both e1 and e2.

Corollary 5.4 follows immediately from 5.1 and 5.3. Corollary 5.3
follows immediately from Corollary 5.2. Corollary 5.2 follows from 5.1
applied to the graph obtained by deleting node v and the edges hitting v,
letting edge e1 join nodes a and b, and letting edge e2 join nodes c and d.
(Oh dear! We might again get more than one edge joining the same two
nodes, but a trivial change in the proof of Theorem 5 proves it for
multigraphs.) Corollary 5.1 follows immediately from Theorem 5 by ignoring
edges e1 and e2 to get G from G'.

Doug West in [6], independently of [1], says "Consider the question:
When can the edges in a pair of hamiltonian circuits be redistributed to
form another pair of circuits with the same union and intersection? A
class of pairs is exhibited which intersect in two edges and cannot be
rearranged in this way."
He observes that for a pair of hamiltonian circuits H1 and H2 of a
graph G, NOT being able to rearrange them in this way is a necessary
condition for H1 and H2 to be adjacent vertices in the graph of edges and
vertices of the convex hull of the (usual 0-1 representation of)
hamiltonian circuits of G. He says "Determining the adjacency structure of
this polytope is extremely difficult" and "The problem of whether an
arbitrary pair of hamiltonian circuits can be rearranged in this way is
quite difficult. Papadimitriou [5] mentions some complexity results. The
conjecture that all edge-disjoint pairs are rearrangeable was raised by Lin
(in 1965) and has been outstanding for a number of years. We extend this
conjecture to to include all pairs whose intersection contains exactly one
edge."
West's conjecture can be strengthened to the following corollary of
5.1:

Corollary 5.5. For a graph G with an edge e which meets edges d1 and
d2 at one end, and which meets edges f1 and f2 at the other end, there is
an even number of ways that G is the union of two hamiltonian circuits, C1
and C2, of G such that the intersection of C1 and C2 is edge e, and such
that d1 and f1 are adjacent to e in C1, and such that d2 and f2 are
adjacent to e in C2.

Proof. Obtain G' from G by replacing [d1, e, f1] by an edge e1, and
replacing [d2, e, f2] by an edge e2. Apply 5.1 and translate the result
back to G.

6. Theorem 6 [Berman,4, when k(v) is odd for every v].
For any graph G with at least three nodes, and a specified pair of numbers
(h(v),k(v)) for each node v of G, such that h(v)+k(v) is the degree of v in
G, and such that for each v either h(v)=1 or k(v) is odd (perhaps both),
there is an even number of partitions of the edges of G into a spanning
tree H of G which has degrees h(v) at nodes v and a subgraph K of G which
has degrees k(v) at nodes v.

An exchange graph X for Theorem 6. The odd-degree vertices of X are the
spanning trees H which have degrees h(v) at all nodes v of G. Choose any
node w such that k(w) is odd to be a fixed special node. The even-degree
vertices of X are the spanning trees H of G which have degree h(w)+1 at
node w, degree h(u)-1 at some node u, and degree h(v) at every other node v
of G. Two vertices of X are joined by an edge in X when each, a spanning
tree of G, can be obtained from the other by exchanging one edge in the one
tree for one edge of the other tree.

Proof of Theorem 6. Each edge of X corresponds to a spanning connected
subgraph L of G with exactly two nodes, w and say x, which have degrees
different from h, in particular h(w)+1 and h(x)+1, and such that x is in
the unique circuit C of L. Each of the two vertices of X met by an edge L
of X, is obtained from L by removing one of the two edges, say edge g of G,
which is in the circuit of L and hits node x. If the other end of g is w,
the resulting spanning tree of G is a vertex of the kind called "odd".
Otherwise the resulting spanning tree is a vertex of the kind called
"even", and the other end of g is the node u which has degree h(u)-1 in
this tree. Each vertex H called "odd" is of odd degree in X, and each
vertex H called "even" is of even degree in X, because: an edge g of G can
be adjoined to an "odd" H to get an L iff g is one of the k(w) edges of G
not in H which hits node w; and an edge g of G can be adjoined to an "even"
H to get an L iff g is one of the k(u)+1 edges of G not in H which hit node
u. For "even" H, the degree of vertex H in X is indeed even, since the
number k(u)+1 is even, since the degree, h(u)-1, of u in H is not 0, since
u is not an isolated node of H, since H is a spanning tree of G. End of
proof of Theorem 6.

Theorem 0 is the case of Theorem 6 where h(v)=2 for all but two nodes
a and b of G (i.e., where in the G of Theorem 6, the odd H's of Theorem 6
are the hamiltonian paths from a to b).

Our exchange graphs X for Theorem 6 are more versatile than the
lollipop graph even for Smith's theorem, i.e., where k(v)=1 for each node v
of G and where the odd vertices H of X are the hamiltonian paths from node
a to b (h(v)=2 except for nodes a and b).
We suspect it will be difficult to prove, one way or the other,
whether there exists a sequence of graphs G, and k(v)=1 for each node v of
G, such that, for every possible choice of node w in G, the exchange graph
X in our proof of Theorem 6 is such that the path between a pair of
1-degree vertices of X grows exponentially. We suspect it will be
difficult to show that the algorithm provided by these X's, one for each
choice of w, is not polytime for, given a hamiltonian circuit H+e in a
cubic graph, find some other one, H'+e.

7. Epilogue. In [10] we presented the concept of "existentially polytime
theorem" as a generalization of "good characterization" (which Edmonds
presented 25 years previously). The story of our mathematical life has
been trying to learn proofs which provide polytime algorithms for finding
an instance of that which EP theorems say exists. One of the types of EP
theorem for which polytime-algorithm proofs seem elusive takes the form:
"For any R, and T in R, there is another T in R" as a corollary of "For
any R, there is an even number of T's in R." Remarkably, no polytime
algorithm is known for, given a cubic graph G and a hamiltonian circuit H+e
of G containing edge e, finding some other hamiltonian circuit H'+e.
An EP search problem is a problem which can be expressed in the form
"for any input x satisfying condition C(x), find a polynomial-size output y
which satisfies condition D(x,y)", where there is a polytime decision
algorithm for C(x), where there is a polytime decision algorithm for
D(x,y), and where the corresponding EP theorem says "for any x satisfying
C(x), there is a polynomial-size y satisfying D(x,y)."
The appropriate EP theorem, and corresponding EP search problem, which
is corollary to Theorem 6, is where C(x) says that x is an instance of
(G,h,k,H) as described in Theorem 6, and where D(x,y) says that y is
another H as in Theorem 6.
It does not seem likely that there is an "NP-hard" EP search problem.
Even assuming the availability of an oracle for every EP search problem,
it does not seem likely to help in getting a polytime algorithm for finding
a hamiltonian path in any given graph which has one. ("If a graph has a
hamiltonian circuit then it has a hamiltonian circuit" is not an EP theorem
unless it turns out that there is a polytime algorithm for deciding whether
or not a graph has a hamiltonian circuit.)
It also seems unlikely that there is an EP problem which is "complete"
in the sense that polytime solving it will polytime solve all other EP
problems. There may be EP theorems which absolutely have no proofs at all,
much less polytime algorithmic proofs. However for any known EP theorem, or
EP conjecture, it seems reasonable to hope to find a proof which provides a
polytime algorithm for the corresponding EP search problem. A number of
prominent computing theorists seem to be active in obtaining reductions
involving some kinds of EP search problems which are not known to have
polytime algorithms [11,12].

References
1. A. G. Thomason, Hamilton cycles and uniquely edge-colourable graphs,
Annals of Discrete Mathematics 3 (1978), 259-268.
2. S. Toida, Properties of an Euler graph, J. Franklin Instititute 295
(1973), 343-345.
3. J. A. Bondy and F. Y. Halberstam, Parity theorems for paths and
cycles in graphs,
J. Graph Theory 10 (1986), 107-115.
4. Kenneth A. Berman, Parity results on connected f-factors, Discrete
Math. 59 (1986), 1-8.
5. Kathie Cameron, Krawczyk's graphs show Thomason's algorithm for
finding a second
hamilton cycle through a given edge in a cubic graph is exponential,
Fifth Czech-Slovak
Symposium on Combinatorics, Graph Theory, Algorithms and
Applications, Prague;
SIAM Conference on Discrete Mathematics, Toronto; July 1998.
6. Douglas B. West, Pairs of adjacent hamiltonian circuits with small
intersection,
Studies in Applied Math. 59 (1978), 245-248.
7. N. J. A. Sloane, Hamiltonian cycles in a graph of degree 4,
J. Combinatorial Theory 6 (1969), 311-312.
8. M. Chrobak and S. Poljak, On common edges in optimal solutions to
traveling salesman
and other optimization problems, Discrete Applied. Math. 20 (1988),
101-111.
9. Christos H. Papadimitriou, On the complexity of the local structure
of certain convex
polytopes, Math. Programming14 (1978), 312-324.
10. Kathie Cameron and Jack Edmonds, Existentially polytime theorems,
DIMACS Series
Discrete Mathematics and Theoretical Computer Science 1 (1990),
83-99.
11. Christos H. Papadimitriou, On the complexity of the parity argument
and other
inefficient proofs of existence, J. Computer and System Sci. 48
(1994), 498-532.
12. Paul Beame, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, Toniann
Pitassi,
The relative complexity of NP search problems, Proc. 27th ACM STOC,
1995,
pp.303-314.