# 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