CSE 2321 Lecture Notes - Lecture 32: Graph Coloring, Complete Bipartite Graph
4 views6 pages
Published on 30 Nov 2019
School
Department
Course
Professor
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
!
Lecture 32
Hamiltonian path Apath in a
graph that visits each vertex
exactly once
M
y
xy
Hamiltonian Cylde AHamiltonian
path that starts and ends on
the same vertex
yA
u
Dirac's Theorem If each vertex of a
connected graph wuverticies is
adjacent to at least up verticies
then the graph has an HC
apple
In Gng 2EdegCv fos VE
So Cy't has an HC
the condition of Dirac's term is
sufficient not necessary sufficient
Take the ceiling if 42 is odd
0O
OOnot an HC
fIIignies
V