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 "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.