Graph Theory – MATH 3260
Lecture 6
Paul Szeptycki
York University
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
William R. Hamilton
Irish algebraist best known for discovering the Quaternian group
(non-abelian generalization of the complex numbers) and studying
symmetry groups, especially of platonic solids.
He was interested in studying the group of symmetries of the
dodecahedron (12 sided platonic solid with all faces pentagons)
For this he needed a trail in the edge graph of the dodecahedron:
a0
a1
a2
a3
a4
c0
c1
c2
c3
c4
b0
b1
b2
b3
b4
d0
d1
d2
d3
d4
That visited each vertex exactly once.
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
William R. Hamilton
Irish algebraist best known for discovering the Quaternian group
(non-abelian generalization of the complex numbers) and studying
symmetry groups, especially of platonic solids.
He was interested in studying the group of symmetries of the
dodecahedron (12 sided platonic solid with all faces pentagons)
For this he needed a trail in the edge graph of the dodecahedron:
a0
a1
a2
a3
a4
c0
c1
c2
c3
c4
b0
b1
b2
b3
b4
d0
d1
d2
d3
d4
That visited each vertex exactly once.
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
William R. Hamilton
Irish algebraist best known for discovering the Quaternian group
(non-abelian generalization of the complex numbers) and studying
symmetry groups, especially of platonic solids.
He was interested in studying the group of symmetries of the
dodecahedron (12 sided platonic solid with all faces pentagons)
For this he needed a trail in the edge graph of the dodecahedron:
a0
a1
a2
a3
a4
c0
c1
c2
c3
c4
b0
b1
b2
b3
b4
d0
d1
d2
d3
d4
That visited each vertex exactly once.
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Hamiltonian cycles
Definition
A closed trail in a graph that passes through each vertex exactly
once is called a Hamiltonian cycle. A non-closed trail that passes
through every vertex exactly once is a Hamiltonian path.
A graph with a Hamiltonian cycle is called Hamiltonian.
A non-Hamiltonian graph with a Hamiltonian path is called
semi-Hamiltonian.
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Hamiltonian cycles
Definition
A closed trail in a graph that passes through each vertex exactly
once is called a Hamiltonian cycle. A non-closed trail that passes
through every vertex exactly once is a Hamiltonian path.
A graph with a Hamiltonian cycle is called Hamiltonian.
A non-Hamiltonian graph with a Hamiltonian path is called
semi-Hamiltonian.
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Hamiltonian cycles
Definition
A closed trail in a graph that passes through each vertex exactly
once is called a Hamiltonian cycle. A non-closed trail that passes
through every vertex exactly once is a Hamiltonian path.
A graph with a Hamiltonian cycle is called Hamiltonian.
A non-Hamiltonian graph with a Hamiltonian path is called
semi-Hamiltonian.
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Some examples
1 The edge graph of a dodecahedron is Hamiltonian
2 The Mo¨bius ladder Mn, n even. Defined by adding edges
between opposite vertices in Cn.
3 The k-cubes.
4 The bow tie.
Observation If a graph has a cut-vertex, then it is not Hamiltonian
v0
v1
v2v3
w0
w1
w2w3
If G S has more than |S | components then G is not Hamiltonian
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Some examples
1 The edge graph of a dodecahedron is Hamiltonian
2 The Mo¨bius ladder Mn, n even. Defined by adding edges
between opposite vertices in Cn.
3 The k-cubes.
4 The bow tie.
Observation If a graph has a cut-vertex, then it is not Hamiltonian
v0
v1
v2v3
w0
w1
w2w3
If G S has more than |S | components then G is not Hamiltonian
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Some examples
1 The edge graph of a dodecahedron is Hamiltonian
2 The Mo¨bius ladder Mn, n even. Defined by adding edges
between opposite vertices in Cn.
3 The k-cubes.
4 The bow tie.
Observation If a graph has a cut-vertex, then it is not Hamiltonian
v0
v1
v2v3
w0
w1
w2w3
If G S has more than |S | components then G is not Hamiltonian
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Some examples
1 The edge graph of a dodecahedron is Hamiltonian
2 The Mo¨bius ladder Mn, n even. Defined by adding edges
between opposite vertices in Cn.
3 The k-cubes.
4 The bow tie.
Observation If a graph has a cut-vertex, then it is not Hamiltonian
v0
v1
v2v3
w0
w1
w2w3
If G S has more than |S | components then G is not Hamiltonian
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Some examples
1 The edge graph of a dodecahedron is Hamiltonian
2 The Mo¨bius ladder Mn, n even. Defined by adding edges
between opposite vertices in Cn.
3 The k-cubes.
4 The bow tie.
Observation If a graph has a cut-vertex, then it is not Hamiltonian
v0
v1
v2v3
w0
w1
w2w3
If G S has more than |S | components then G is not Hamiltonian
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Some examples
1 The edge graph of a dodecahedron is Hamiltonian
2 The Mo¨bius ladder Mn, n even. Defined by adding edges
between opposite vertices in Cn.
3 The k-cubes.
4 The bow tie.
Observation If a graph has a cut-vertex, then it is not Hamiltonian
v0
v1
v2v3
w0
w1
w2w3
If G S has more than |S | components then G is not Hamiltonian
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Some examples
1 The edge graph of a dodecahedron is Hamiltonian
2 The Mo¨bius ladder Mn, n even. Defined by adding edges
between opposite vertices in Cn.
3 The k-cubes.
4 The bow tie.
Observation If a graph has a cut-vertex, then it is not Hamiltonian
v0
v1
v2v3
w0
w1
w2w3
If G S has more than |S | components then G is not Hamiltonian
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Peterson Graph
Is it Hamiltonian?
What cycles appear in the Peterson Graph?
1 Any 3 cycles?
2 Any 4 cycles?
3 Any 5 cycles?
4 Any 6 cycles?
5 7,8,9,10?
In summary, the Peterson Graph contains no 3,4,7 or 10 cycles, but
contains the 5,6,8 and 9 cycles
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Peterson Graph
Is it Hamiltonian?
What cycles appear in the Peterson Graph?
1 Any 3 cycles?
2 Any 4 cycles?
3 Any 5 cycles?
4 Any 6 cycles?
5 7,8,9,10?
In summary, the Peterson Graph contains no 3,4,7 or 10 cycles, but
contains the 5,6,8 and 9 cycles
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Peterson Graph
Is it Hamiltonian?
What cycles appear in the Peterson Graph?
1 Any 3 cycles?
2 Any 4 cycles?
3 Any 5 cycles?
4 Any 6 cycles?
5 7,8,9,10?
In summary, the Peterson Graph contains no 3,4,7 or 10 cycles, but
contains the 5,6,8 and 9 cycles
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Peterson Graph
Is it Hamiltonian?
What cycles appear in the Peterson Graph?
1 Any 3 cycles?
2 Any 4 cycles?
3 Any 5 cycles?
4 Any 6 cycles?
5 7,8,9,10?
In summary, the Peterson Graph contains no 3,4,7 or 10 cycles, but
contains the 5,6,8 and 9 cycles
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Peterson Graph
Is it Hamiltonian?
What cycles appear in the Peterson Graph?
1 Any 3 cycles?
2 Any 4 cycles?
3 Any 5 cycles?
4 Any 6 cycles?
5 7,8,9,10?
In summary, the Peterson Graph contains no 3,4,7 or 10 cycles, but
contains the 5,6,8 and 9 cycles
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Peterson Graph
Is it Hamiltonian?
What cycles appear in the Peterson Graph?
1 Any 3 cycles?
2 Any 4 cycles?
3 Any 5 cycles?
4 Any 6 cycles?
5 7,8,9,10?
In summary, the Peterson Graph contains no 3,4,7 or 10 cycles, but
contains the 5,6,8 and 9 cycles
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Peterson Graph
Is it Hamiltonian?
What cycles appear in the Peterson Graph?
1 Any 3 cycles?
2 Any 4 cycles?
3 Any 5 cycles?
4 Any 6 cycles?
5 7,8,9,10?
In summary, the Peterson Graph contains no 3,4,7 or 10 cycles, but
contains the 5,6,8 and 9 cycles
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Peterson Graph
Is it Hamiltonian?
What cycles appear in the Peterson Graph?
1 Any 3 cycles?
2 Any 4 cycles?
3 Any 5 cycles?
4 Any 6 cycles?
5 7,8,9,10?
In summary, the Peterson Graph contains no 3,4,7 or 10 cycles, but
contains the 5,6,8 and 9 cycles
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Dirac’s Theorem
Theorem (Dirac)
If G is a simple graph with n 3 vertices and if deg(v) 12n for
every vertex v , then G is Hamiltonian.
This follows from the more general (but proved later):
Theorem (Ore)
If G is a simple graph with n 3 vertices and if
deg(v) + deg(w) n
for each pair of nonadjacent vertices v and w , then G is
Hamilitonian.
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Dirac’s Theorem
Theorem (Dirac)
If G is a simple graph with n 3 vertices and if deg(v) 12n for
every vertex v , then G is Hamiltonian.
This follows from the more general (but proved later):
Theorem (Ore)
If G is a simple graph with n 3 vertices and if
deg(v) + deg(w) n
for each pair of nonadjacent vertices v and w , then G is
Hamilitonian.
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Hamiltonian digraphs
The following generalization of Dirac’s theorem is too involved for
us to prove.
Theorem
If G is a strongly connected digraph with n vertices. If
outdeg(v) 12n and indeg(v) 12n, then G has a directed
Hamiltonian cycle.
Example A tournament is a directed graph whose underlying
graph is a complete.
Observation Even a tournament can’t satisfy the hypothesis of
the above Theorem
However,
Theorem
Every tournament is either Hamiltonian or semi-Hamiltonian. And
a strongly connected tournament is Hamiltonian.
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Hamiltonian digraphs
The following generalization of Dirac’s theorem is too involved for
us to prove.
Theorem
If G is a strongly connected digraph with n vertices. If
outdeg(v) 12n and indeg(v) 12n, then G has a directed
Hamiltonian cycle.
Example A tournament is a directed graph whose underlying
graph is a complete.
Observation Even a tournament can’t satisfy the hypothesis of
the above Theorem
However,
Theorem
Every tournament is either Hamiltonian or semi-Hamiltonian. And
a strongly connected tournament is Hamiltonian.
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Hamiltonian digraphs
The following generalization of Dirac’s theorem is too involved for
us to prove.
Theorem
If G is a strongly connected digraph with n vertices. If
outdeg(v) 12n and indeg(v) 12n, then G has a directed
Hamiltonian cycle.
Example A tournament is a directed graph whose underlying
graph is a complete.
Observation Even a tournament can’t satisfy the hypothesis of
the above Theorem
However,
Theorem
Every tournament is either Hamiltonian or semi-Hamiltonian. And
a strongly connected tournament is Hamiltonian.
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6
Hamiltonian digraphs
The following generalization of Dirac’s theorem is too involved for
us to prove.
Theorem
If G is a strongly connected digraph with n vertices. If
outdeg(v) 12n and indeg(v) 12n, then G has a directed
Hamiltonian cycle.
Example A tournament is a directed graph whose underlying
graph is a complete.
Observation Even a tournament can’t satisfy the hypothesis of
the above Theorem
However,
Theorem
Every tournament is either Hamiltonian or semi-Hamiltonian. And
a strongly connected tournament is Hamiltonian.
Paul Szeptycki Graph Theory – MATH 3260 Lecture 6

欢迎咨询51作业君