BEAUTIFUL CONJECTURES What is a beautiful conjecture?
IN
The mathematician’s patterns, like the painter’s or the poet’s
GRAPH THEORY must be beautiful; the ideas, like the colors or the words must fit
together in a harmonious way. Beauty is the first test: there is
no permanent place in this world for ugly mathematics.
G.H. Hardy
Adrian Bondy
Some criteria:
Reconstruction Conjecture
. Simplicity: short, easily understandable statement relating P.J. Kelly and S.M. Ulam 1942
basic concepts.
. Element of Surprise: links together seemingly disparate
Every simple graph on at least three vertices is
concepts.
reconstructible from its vertex-deleted subgraphs
. Generality: valid for a wide variety of objects.
. Centrality: close ties with a number of existing theorems
and/or conjectures.
. Longevity: at least twenty years old.
. Fecundity: attempts to prove the conjecture have led to new
concepts or new proof techniques.
STANISLAW ULAM
Simple Surprising General Central Old F ertile
∗∗ ∗∗∗ ∗∗∗
v1 v2
v6 v3
Edge Reconstruction Conjecture
F. Harary 1964
v5 v4
G
Every simple graph on at least four edges is
reconstructible from its edge-deleted subgraphs
G − v1 G − v2 G − v3
PSfrag replacements
FRANK HARARY
G − v4 G − v5 G − v6
Simple Surprising General Central Old F ertile
∗∗∗ ∗∗∗ ∗∗ ∗
MAIN FACTS
Reconstruction Conjecture
G H
False for digraphs. There exist infinite
families of nonreconstructible tournaments.
P.J. Stockmeyer 1977
PSfrag replacements
G H Edge Reconstruction Conjecture
True for graphs on n vertices and more
than n log2 n edges.
L. Lovász 1972, V. Müller 1977
Path Decompositions Circuit Decompositions
T. Gallai 1968 G. Hajós 1968
Every connected simple graph on n vertices can Every simple even graph on n vertices can be
be decomposed into at most 21 (n + 1) paths decomposed into at most 12 (n − 1) circuits
TIBOR GALLAI
György Hajós
Simple Surprising General Central Old F ertile
∗∗∗ ∗∗∗ ∗ ∗∗ ∗∗ Simple Surprising General Central Old F ertile
∗∗∗ ∗ ∗ ∗∗ ∗∗
MAIN FACTS
Hamilton Decompositions
P.J. Kelly 1968
Every regular tournament can be decomposed Gallai’s Conjecture
into directed Hamilton circuits.
True for graphs in which all degrees are odd.
L. Lovász 1968
Hajós’ Conjecture
True for planar graphs and for graphs with
maximum degree four.
J. Tao 1984,
Kelly’s Conjecture
Claimed true for very large tournaments.
Simple Surprising General Central Old F ertile R. Häggkvist (unpublished)
∗∗∗ ∗∗∗ ∗ ∗ ∗∗ ∗
Circuit Double Cover Conjecture
P.D. Seymour 1979
Every graph without cut edges has a double
covering by circuits.
Paul Seymour
Simple Surprising General Central Old F ertile
∗∗∗ ∗∗ ∗∗∗ ∗∗∗ ∗ ∗∗∗
Small Circuit Double Cover Cycle Double Cover Conjecture
Conjecture M. Preissmann 1981
JAB 1990
Every graph without cut edges has a double
Every simple graph on n vertices without cut covering by at most five even subgraphs
edges has a double covering by at most n − 1
circuits.
Myriam Preissmann
Simple Surprising General Central Old F ertile
JAB ∗∗∗ ∗∗∗ ∗∗∗ ∗∗ ∗ ∗
Simple Surprising General Central Old F ertile
∗∗∗ ∗∗ ∗∗∗ ∗∗ ∗ ∗
Matching Double Cover Conjecture
R.D. Fulkerson 1971
Every cubic graph without cut edges has a double
covering by six perfect matchings
PSfrag replacements
REFORMULATION:
G
H
Cycle Quadruple Cover Conjecture
PETERSEN GRAPH F. Jaeger 1985
Every graph without cut edges has a quadruple
covering by six even subgraphs
Simple Surprising General Central Old F ertile
∗∗∗ ∗ ∗∗ ∗ ∗∗ ∗
MAIN FACTS
Five-Flow Conjecture
W.T. Tutte 1954
Circuit Double Cover Conjecture
If false, a minimal counterexample must Every graph without cut edges has a 5-flow
have girth at least ten.
L. Goddyn 1988
Small Circuit Double Cover
Conjecture
True for graphs in which some vertex is
adjacent to every other vertex.
H. Li 1990
Cycle Double Cover Conjecture
True for 4-edge-connected graphs. Bill Tutte
P.A. Kilpatrick 1975, F. Jaeger 1976
True for various classes of snarks. Simple Surprising General Central Old F ertile
U. Celmins 1984 ∗∗∗ ∗∗∗ ∗∗∗ ∗∗∗ ∗∗∗ ∗∗∗
Cycle Quadruple Cover Conjecture
Every graph without cut edges has a
quadruple covering by seven even subgraphs.
J.C. Bermond, B. Jackson and F. Jaeger 1983
4 3 2
2 4 1
1 1 1
1 1
3 2 2
2
1
1 2
2
PSfrag replacements
1 1 3 1 1 1
1
3 3
2
PSfrag replacements
2 2
1
WEAKER CONJECTURE:
Three-Flow Conjecture
W.T. Tutte 1954
Every 4-edge-connected graph has a 3-flow Weak Three-Flow Conjecture
F. Jaeger, 1976
There exists an integer k such that every
k-edge-connected graph has a 3-flow
Bill Tutte
Simple Surprising General Central Old F ertile
∗∗∗ ∗∗∗ ∗∗ ∗∗ ∗∗∗
MAIN FACTS
Directed Cages
M. Behzad, G. Chartrand and C.E. Wall 1970
Five-Flow Conjecture Every d-diregular digraph on n vertices has a
directed circuit of length at most dn/de
Every graph without cut edges has a 6-flow.
P.D. Seymour 1981
Three-Flow Conjecture
Every 4-edge-connected graph has a 4-flow.
F. Jaeger 1976
Extremal graph for d = dn/3e
(directed triangle)
Simple Surprising General Central Old F ertile
∗∗ ∗ ∗ ∗∗ ∗∗
Second Neighbourhoods
P.D. Seymour 1990 v
Every digraph without 2-circuits has a vertex
with at least as many second neighbours as first PSfrag replacements
neighbours
Paul Seymour
Simple Surprising General Central Old F ertile
∗∗ ∗∗ ∗∗∗ ∗ ∗
The Second Neighbourhood Conjecture MAIN FACTS
implies the case
lnm
d= Behzad-Chartrand-Wall Conjecture
3
of the Directed Cages Conjecture: Every d-diregular digraph on n vertices has
a directed circuit of length at most
n/d + 2500.
V. Chvátal and E. Szemerédi 1983
True for d ≤ 5.
v C. Hoàng and B.A. Reed 1987
d d ≥d
Sfrag replacements Every cn-diregular digraph on n vertices
with c ≥ .34615 has a directed triangle.
M. de Graaf 2004
If no directed triangle Second Neighbourhood Conjecture
True for tournaments.
n ≥ 3d + 1 > n
J. Fisher 1996, [Link] and S. Thomassé 2000
Chords of Longest Circuits Smith’s Conjecture
C. Thomassen 1976 S. Smith 1984
Every longest circuit in a 3-connected graph has In a k-connected graph, where k ≥ 2, any two
a chord longest circuits have at least k vertices in
common
Carsten Thomassen Scott Smith
Simple Surprising General Central Old F ertile Simple Surprising General Central Old F ertile
∗∗∗ ∗∗ ∗ ∗ ∗∗∗ ∗ ∗∗∗ ∗
Hamilton Circuits in Line Graphs
C. Thomassen 1986
Every 4-connected line graph is hamiltonian
Carsten Thomassen
Simple Surprising General Central Old F ertile
∗∗∗ ∗ ∗ ∗ ∗ ∗
MAIN FACTS
Hamilton Circuits in Claw-Free
Graphs
M. Matthews and D. Sumner 1984
Thomassen’s Chord Conjecture
Every 4-connected claw-free graph is hamiltonian
True for bipartite graphs.
C. Thomassen 1997
Simple Surprising General Central Old P rolif ic
∗ ∗ ∗∗ ∗ Scott Smith’s Conjecture
True for k ≤ 6.
M. Grötschel 1984
Thomassen’s Line Graph Conjecture
Line graphs of 4-edge-connected graphs are
hamiltonian.
C. Thomassen 1986
Every 7-connected line graph is hamiltonian.
S.M. Zhan 1991
Hamilton Circuits in Regular
Graphs
J. Sheehan 1975
Every simple 4-regular graph with a Hamilton
circuit has a second Hamilton circuit
AN INTERESTING GRAPH
Used by Fleischner to construct a 4-regular
multigraph with exactly one Hamilton circuit.
John Sheehan
Simple Surprising General Central Old F ertile
∗∗∗ ∗∗ ∗ ∗ ∗∗
Finding a Second Hamilton Circuit Hamilton Circuits in 4-Connected
M. Chrobak and S. Poljak 1988 Graphs
H. Fleischner 2004
Given a Hamilton circuit in a 3-regular graph,
find (in polynomial time) a second Hamilton Every 4-connected graph with a Hamilton circuit
circuit has a second Hamilton circuit
Herbert Fleischner
Marek Chrobak and Svatopluk Poljak
Simple Surprising General Central Old F ertile
∗∗∗ ∗∗ ∗ ∗
Simple Surprising General Central Old F ertile
∗∗∗ ∗ ∗ ∗ ∗
MAIN FACTS What is a beautiful theorem?
Mathematics, rightly viewed, possesses not only truth, but
supreme beauty – a beauty cold and austere, like that of
Sheehan’s Conjecture sculpture.
Every simple 300-regular graph with a Bertrand Russell
Hamilton circuit has a second Hamilton
circuit. Some criteria:
C. Thomassen 1998
. Simplicity: short, easily understandable statement relating
There exist simple uniquely hamiltonian basic concepts.
graphs of minimum degree four. . Element of Surprise: links together seemingly disparate
concepts.
H. Fleischner 2004
. Generality: valid for a wide variety of objects.
. Centrality: close ties with a number of existing theorems
and/or conjectures.
Fleischner’s Conjecture
. Fecundity: has inspired interesting extensions and/or
True for planar graphs. generalizations.
. Correctness: a beautiful theorem should be true!
W.T. Tutte 1956
What is a beautiful proof?
Most Beautiful Conjecture
J.A.B.
. . . an elegant proof is a proof which would not normally come
to mind, like an elegant chess problem: the first move should be
paradoxical . . . Dominic will continue to prove and conjecture
for many years to come
Claude Berge
Claude Berge
HAPPY BIRTHDAY, DOMINIC!
Some criteria:
. Elegance: combination of simplicity and surprise.
. Ingenuity: inspired use of standard techniques.
. Originality: introduction of new proof techniques.
. Fecundity: inspires new proof techniques or new proofs of
existing theorems.
. Correctness: a beautiful proof should be correct!
