The lecture on Wednesday Oct. 3,
2-4 PM, is a guest lecture by JACK
EDMONDS on Second Hamiltonian
Paths :
A theorem of
K.Berman,1986, says
If a graph G with Hamiltonian path P is such that G minus the edges of
P is
connected, then G contains another Hamiltonian path P' with the same
endpoints as P.
We would hope to prove this by an easy (i.e. polynomial-time)
algorithm
for finding some P'. So far no easy algorithm is known. I
describe an
algorithm for proving Berman's theorem which is a variation of Andrew
Thomason's beautiful "lollipop method". Kind of like the simplex method
for
linear programming, it has not yet been shown whether or not there is a
non-exponential way to do the algorithm. K.Cameron shows that the
lollipop
method itself is exponential.
A theorem is called "existentially polytime" (EP) if it asserts
the
existence of something which is easy to recognize when you have
it. Very
often an EP theorem can be proved by a polynomial-time algorithm which
finds
an instance of what it says exists. However, Berman's theorem is
one of
many EP theorems which has not yet been proved by a provably easy
algorithm.
The book "Digraphs" by Bang-Jensen and Gutin has many theorems
related to
Hamiltonian paths. It's interesting to study which theorems in the book
can
be put into an EP form, and which of them have proofs which are
essentially
polynomial-time algorithms for finding an instance of what is asserted
to
exist.
The exercises on Monday Oct. 9, 10-12 AM, will deal with
The sequence of problems 1, 2, 3, ...Problem 7 asks for a proof of Petersen's Even factor Theorem (that any 2r-regular graph can be factorized into r 2-factors).
Problem 1: The sum of the degrees in any graph is an even number.
Any graph has an even number of vertices of odd degree.
Problem 2:
A graph where alle vertices have even degree cannot have a bridge (a
bridge is an edge xy whose removal leaves x and y in different
components of the remaining graph).
Problem 3. Let G be a graph
with at least one edge and all degrees even. Prove that G has a
closed Eulerian trail (a sequence of different consequtive edges,
covering each edge of G exactly once, and ending in the vertex where
it started). This is EULER's THREOREM.
Problem 4: Any 4-regular
graph may be divided into two 2-factors.
Problem 5: In a graph of
maximum degree 4 the edge set may be divided into two classes, such
that any vertex of the graph is incident with at most two edges from
each class.
Problem 6: In a graph of maximum degree 2r the edgeset
may be divided into r classes, such that any vertex of the graph is
incident with at most two edges from each class.
Problem 7: Any
2r-regular graph may be divided into r 2-factors.
Loose ends