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作业君
