Ta
.
p ch´ı Tin ho
.
c v`a Diˆe
`
u khiˆe
’
n ho
.
c, T.22, S.3 (2006), 221—228
S
ˆ
O
´
D
ˆ
O
`
THI
.
HAMILTON T
ˆ
O
´
I DA
.
I
V
˜
U D

`
INH H
`
OA
1
, D
ˆ
O
˜
NHU
.
AN
2
1
Khoa Cˆong nghˆe
.
thˆong tin, Tru
.
`o
.
ng
Da
.
i ho
.
c Su
.
pha
.
m H`a Nˆo

.
i
2
Khoa Cˆong nghˆe
.
thˆong tin, Tru
.
`o
.
ng
Da
.
i ho
.
c Nha Trang
Abstract. A graph is called a
maximal uniquely Hamiltonian graph
if it has the maximum number
of edges among the graphs with the same number of vertices and exact one Hamiltonian cycle. In this
paper, we prove the conjecture posed in [5] that for every
n ≥ 7
there are exactly
2
[
n−7
2
]
maximal
uniquely Hamiltonian graphs.
T´om t˘a

´
t. Mˆo
.
t
dˆo
`
thi
.
du
.
o
.
.
c go
.
i l`a
dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i nˆe
´
u nhu
.
n´o c´o sˆo
´

ca
.
nh nhiˆe
`
u nhˆa
´
t c´o thˆe
’
trong c´ac
dˆo
`
thi
.
c´o c`ung sˆo
´
dı
’
nh v`a c´o d´ung mˆo
.
t chu tr`ınh Hamilton. Trong b`ai n`ay, ch´ung tˆoi ch´u
.
ng
minh gia
’
thuyˆe
´
t
du
.
o

.
.
c nˆeu trong [5] r˘a
`
ng c´o
d´ung
2
[
n−7
2
]
dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i
n ≥ 7
dı
’
nh.
1. MO
.
’
D
ˆ
A

`
U
Trong b`ai b´ao n`ay, ch´ung ta chı
’
n´oi
dˆe
´
n c´ac dˆo
`
thi
.
h˜u
.
u ha
.
n vˆo hu
.
´o
.
ng. Mˆo
.
t
dˆo
`
thi
.
G
du
.
o

.
.
c
k´y hiˆe
.
u
G = (V, E)
v´o
.
i
V
l`a tˆa
.
p ho
.
.
p
dı
’
nh v`a
E
l`a tˆa
.
p ho
.
.
p ca
.
nh cu
’

a
G
. Dˆo
`
thi
.
G
1
= (V
1
, E
1
)
du
.
o
.
.
c n´oi l`a
dˆo
`
thi
.
con cu
’
a dˆo
`
thi
.
G

2
= (V
2
, E
2
)
nˆe
´
u nhu
.
V
1
⊆ V
2
v`a
E
1
⊆ E
2
. Dˆo
`
thi
.
con
G
1
= (V
1
, E
1

)
cu
’
a dˆo
`
thi
.
G
2
= (V
2
, E
2
)
du
.
o
.
.
c go
.
i l`a
dˆo
`
thi
.
th`anh phˆa
`
n cu
’

a
G
2
nˆe
´
u nhu
.
mˆo
˜
i
ca
.
nh
e = (x, y)
cu
’
a
G
2
v´o
.
i
x, y ∈ V
1
c˜ung l`a ca
.
nh cu
’
a dˆo
`

thi
.
G
1
. Cho tru
.
´o
.
c
dˆo
`
thi
.
G = (V, E)
v`a
S
l`a tˆa
.
p ho
.
.
p con cu
’
a
V
, th`ı dˆo
`
thi
.
th`anh phˆa

`
n cu
’
a
G
v´o
.
i tˆa
.
p
dı
’
nh
S
du
.
o
.
.
c go
.
i l`a
dˆo
`
thi
.
sinh bo
.
’
i

S
v`a du
.
o
.
.
c k´y hiˆe
.
u l`a
G[S]
. Ngo`ai ra, mo
.
i k´y hiˆe
.
u v`a kh´ai niˆe
.
m kh´ac o
.
’
dˆay dˆe
`
u du
.
o
.
.
c
lˆa
´
y t`u

.
[3]. Cho tru
.
´o
.
c mˆo
.
t
dˆo
`
thi
.
do
.
n vˆo hu
.
´o
.
ng
G
, ta go
.
i mˆo
.
t chu tr`ınh
C
cu
’
a
G

l`a chu tr`ınh
Hamilton nˆe
´
u n´o
di qua tˆa
´
t ca
’
c´ac dı
’
nh cu
’
a dˆo
`
thi
.
G
. Trong h`ınh 1 ta c´o mˆo
.
t dˆo
`
thi
.
5 dı
’
nh
v´o
.
i hai chu tr`ınh Hamilton kh´ac nhau.
H`ınh 1. Dˆo

`
thi
.
5 dı
’
nh c´o hai chu tr`ınh Hamilton
Dˆo
`
thi
.
khˆong c´o chu tr`ınh Hamilton v´o
.
i nhiˆe
`
u ca
.
nh nhˆa
´
t,
d˜a du
.
o
.
.
c nghiˆen c´u
.
u bo
.
’
i Erdos

[4] v`a mˆo
.
t sˆo
´
nh`a to´an ho
.
c kh´ac. Nˆe
´
u
dˆo
`
thi
.
G
c´o chu tr`ınh Hamilton th`ı n´o du
.
o
.
.
c go
.
i l`a
dˆo
`
thi
.
Hamilton. Mˆo
.
t
dˆo

`
thi
.
chı
’
c´o d´ung mˆo
.
t chu tr`ınh Hamilton du
.
o
.
.
c go
.
i l`a
dˆo
`
thi
.
Hamilton
tˆo
´
i
da
.
i nˆe
´
u nhu
.
n´o c´o nhiˆe

`
u ca
.
nh nhˆa
´
t trong sˆo
´
c´ac
dˆo
`
thi
.
c`ung sˆo
´
dı
’
nh v`a c´o d´ung mˆo
.
t chu
tr`ınh Hamilton. L´o
.
p c´ac
dˆo
`
thi
.
n`ay du
.
o
.

.
c nhiˆe
`
u nh`a to´an ho
.
c nghiˆen c´u
.
u ([1, 2, 5, 6]). H`ınh 2
222
V
˜
U D
`
INH H
`
OA, D
ˆ
O
˜
NHU
.
AN
l`a dˆo
`
thi
.
Hamilton tˆo
´
i da
.

i 5 dı
’
nh.
H`ınh 2. Dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i 5 dı
’
nh
Dˆo
´
i v´o
.
i
dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i, Sheehan [6] d˜a nghiˆen c´u
.
u b`ai to´an t`ım sˆo

´
ca
.
nh nhiˆe
`
u
nhˆa
´
t c´o thˆe
’
cu
’
a
dˆo
`
thi
.
n
dı
’
nh v´o
.
i duy nhˆa
´
t mˆo
.
t chu tr`ınh Hamilton. Kˆe
´
t qua
’

tu
.
o
.
ng tu
.
.
du
.
o
.
.
c
Barefoot v`a Entringer [1] nghiˆen c´u
.
u cho l´o
.
p
dˆo
`
thi
.
c´o duy nhˆa
´
t mˆo
.
t chu tr`ınh Hamilton v`a
hai
dı
’

nh khˆong kˆe
`
nhau bˆa
´
t k`y cu
’
a n´o du
.
o
.
.
c nˆo
´
i v´o
.
i nhau bo
.
’
i mˆo
.
t
du
.
`o
.
ng Hamilton (
du
.
`o
.

ng
ch´u
.
a to`an bˆo
.
c´ac
dı
’
nh cu
’
a dˆo
`
thi
.
). Ta khˆong xem x´et l´o
.
p
dˆo
`
thi
.
d´o o
.
’
dˆay.
Sheehan [6] ch´u
.
ng minh
di
.

nh l´y sau:
Di
.
nh l´y 1. [Sheehan] Dˆo
`
thi
.
tˆo
´
i da
.
i v´o
.
i
n
dı
’
nh c´o d´ung
[
n
2
4
] + 1
ca
.
nh.
Trong [5], ch´ung tˆoi
d˜a chı
’
ra r˘a

`
ng c´o ´ıt nhˆa
´
t
2
[
n−7
2
]
dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i b˘a
`
ng thuˆa
.
t
to´an x´ac
di
.
nh dˆo
`
thi
.
Hamilton tˆo

´
i da
.
i
n
dı
’
nh nhu
.
sau.
Di
.
nh l´y 2. Thuˆa
.
t to´an sau dˆay cho ta ´ıt nhˆa
´
t
2
[
n−7
2
]
dˆo
`
thi
.
Hamilton tˆo
´
i da
.

i
n
dı
’
nh khˆong
d˘a
’
ng cˆa
´
u v´o
.
i nhau.
Xuˆa
´
t ph´at t`u
.
mˆo
.
t chu tr`ınh
C
c´o
n
dı
’
nh. Ta cho
.
n dı
’
nh
x

0
t`uy ´y trˆen
C
v`a x´ac di
.
nh
X
1
= {x
0
},
Y
1
= ∅.
Nˆe
´
u tˆa
.
p dı
’
nh
X
i
v`a
Y
i
d˜a du
.
o
.

.
c x´ac
di
.
nh, th`ı ta x´ac di
.
nh dı
’
nh
x
i
/∈ X
i
sao cho tˆo
`
n ta
.
i
x

∈ X
i
c´ach
x
i
khoa
’
ng c´ach 2 do
.
c theo chu tr`ınh

C
, v`a
y
i
l`a dı
’
nh kˆe
`
v´o
.
i
x
i
v`a
x

trˆen
C
. Tˆa
.
p ho
.
.
p
X
i+1
v`a
Y
i+1
du

.
o
.
.
c x´ac
di
.
nh theo quy t˘a
´
c sau:
X
i+1
= X
i
∪ {x
i
},
Y
i+1
= Y
i
∪ {y
i
},
v´o
.
i
i = 1, 2, . . . , [
n
2

]
. Dˆo
`
thi
.
G
thu du
.
o
.
.
c b˘a
`
ng c´ach bˆo
’
sung v`ao
C
c´ac ca
.
nh nˆo
´
i c´ac dı
’
nh
y
i
v´o
.
i tˆa
´

t ca
’
c´ac c´ac
dı
’
nh khˆong thuˆo
.
c
X
i+1
∪ Y
i+1
. Ch˘a
’
ng ha
.
n trong H`ınh 3, ta c´o hai dˆo
`
thi
.
Hamilton tˆo
´
i
da
.
i 9 dı
’
nh khˆong d˘a
’
ng cˆa

´
u.
v
6
v
1
v
1
v
2
v
2
v
3
v
4
v
5
v
7
v
8
v
9
v
3
v
4
v
5

v
6
v
7
v
8
v
9
v
6
v
1
v
1
v
2
v
2
v
3
v
4
v
5
v
7
v
8
v
9

v
3
v
4
v
5
v
6
v
7
v
8
v
9
H`ınh 3. Hai dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i 9 dı
’
nh
S
ˆ
O
´
D

ˆ
O
`
THI
.
HAMILTON T
ˆ
O
´
I DA
.
I
223
B˘a
`
ng thuˆa
.
t to´an d˜a nˆeu trˆen, ta c´o ´ıt nhˆa
´
t
2
[
n−7
2
]
dˆo
`
thi
.
Hamilton tˆo

´
i da
.
i
n
dı
’
nh cho mˆo
˜
i
gi´a tri
.
n  7
. Trong [5], gia
’
thuyˆe
´
t sau du
.
o
.
.
c
du
.
a ra.
Gia
’
thuyˆe
´

t 1. C´o
d´ung
2
[
n−7
2
]
dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i
n  7
dı
’
nh.
Sau
dˆay ta ch´u
.
ng minh r˘a
`
ng gia
’
thuyˆe
´
t trˆen l`a

d´ung.
Di
.
nh l´y 3. C´o d´ung
2
[
n−7
2
]
dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i
n  7
dı
’
nh.
2. M
ˆ
O
.
T S
ˆ
O
´

K
´
Y HI
ˆ
E
.
U V
`
A K
ˆ
E
´
T QUA
’
CO
.
BA
’
N
K´y hiˆe
.
u
h(n)
l`a sˆo
´
ca
.
nh cu
’
a dˆo

`
thi
.
Hamilton tˆo
´
i da
.
i
n
dı
’
nh. C´ac bˆo
’
dˆe
`
du
.
´o
.
i
dˆay d˜a du
.
o
.
.
c
Sheehan [6] ch´u
.
ng minh.
Bˆo

’
dˆe
`
1. ( Theorem 1 [6])
h(n) = [
n
2
4
] + 1
.
X´et mˆo
.
t
dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i
G
v´o
.
i
n
dı
’
nh. Ta k´y hiˆe

.
u c´ac dı
’
nh cu
’
a
G
liˆen tiˆe
´
p nhau
trˆen chu tr`ınh Hamilton
C
cu
’
a
G
l`a
v
1
, v
2
, . . . , v
n
. Mˆo
˜
i ca
.
nh
e
cu

’
a
G
khˆong thuˆo
.
c
C
c`on
du
.
o
.
.
c go
.
i l`a mˆo
.
t dˆay cung cu
’
a
C
. Ta c´o:
Bˆo
’
dˆe
`
2. (Lemma 2 [6]) Hai dˆay cung
(v
i
, v

j+1
)
,
(v
i+1
, v
j
)
khˆong dˆo
`
ng th`o
.
i thuˆo
.
c
G
.
Cho tru
.
´o
.
c mˆo
.
t dˆay cung
e = (v
i
, v
j
)
, ta go

.
i dˆo
.
d`ai cu
’
a dˆay cung e l`a dˆo
.
d`ai cu
’
a con du
.
`o
.
ng
ng˘a
´
n nhˆa
´
t do
.
c theo
C
nˆo
´
i 2 dı
’
nh cu
’
a
e

, nhu
.
vˆa
.
y
dˆo
.
d`ai

cu
’
a dˆay cung
e
t`uy ´y luˆon l`a mˆo
.
t
sˆo
´
tu
.
.
nhiˆen tho
’
a m˜an
1   
n
2
. Ngu
.
o

.
.
c la
.
i, v´o
.
i mˆo
˜
i sˆo
´
tu
.
.
nhiˆen

tho
’
a m˜an
1   
n
2
, ta
k´y hiˆe
.
u
C(n : )
l`a tˆa
.
p ho
.

.
p c´ac dˆay cung c´o
dˆo
.
d`ai

.
Bˆo
’
dˆe
`
3. (Lemma 3 [6]) V´o
.
i mˆo
˜
i
n
, ta c´o
|C(n : )| 
n
2
.
Ngo`ai ra trong [6] c˜ung ch´u
.
ng minh:
Bˆo
’
dˆe
`
4. (Lemma 6 [6]) Nˆe

´
u
n
l`a sˆo
´
ch˘a
˜
n,

l`a sˆo
´
le
’
tho
’
a m˜an
1   <
n
2
th`ı
|C(n : )| <
n
2
.
Bˆo
’
dˆe
`
5. (Lemma 7 [6]) Nˆe
´

u
n
l`a sˆo
´
ch˘a
˜
n th`ı
|C(n :
n
2
)| 
n
4
.
Trong
dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i v´o
.
i
d´ung
[
n
2

4
] + 1
ca
.
nh, th`ı c´ac bˆa
´
t d˘a
’
ng th´u
.
c
du
.
o
.
.
c ch´u
.
ng
minh trong c´ac bˆo
’
dˆe
`
trˆen tro
.
’
th`anh
d˘a
’
ng th´u

.
c, cho nˆen ta c´o:
Bˆo
’
dˆe
`
6. Trong dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i
G
v´o
.
i
n
dı
’
nh v`a
[
n
2
4
] + 1
ca
.

nh, ta c´o:
a) Nˆe
´
u
n
l`a sˆo
´
le
’
th`ı
G
c´o
n−1
2
dˆay cung dˆo
.
d`ai
 
n
2
.
b) Nˆe
´
u
n
l`a sˆo
´
ch˘a
˜
n th`ı

G
:
- c´o
d´ung
n
4
dˆay cung dˆo
.
d`ai
n
2
ch˘a
˜
n,
- c´o
d´ung
n
2
dˆay cung dˆo
.
d`ai ch˘a
˜
n
 =
n
2
,
- c´o
d´ung
n

2
− 1
dˆay cung dˆo
.
d`ai le
’
 =
n
2
.
Dˆe
’
ch´u
.
ng minh
Di
.
nh l´y 3, ta nghiˆen c´u
.
u cˆa
´
u tr´uc c´ac dˆay cung trong
dˆo
`
thi
.
Hamilton tˆo
´
i
da

.
i
G
.
3. C
ˆ
A
´
U TR
´
UC
D
ˆ
O
`
THI
.
HAMILTON T
ˆ
O
´
I DA
.
I
Cho tru
.
´o
.
c
dˆo

`
thi
.
Hamilton tˆo
´
i da
.
i
G
v´o
.
i
[
n
2
4
] + 1
ca
.
nh, ta biˆe
’
u diˆe
˜
n dˆo
`
thi
.
G
c´o dı
’

nh ta
.
i
dı
’
nh mˆo
.
t
n
gi´ac dˆe
`
u v`a ca
.
nh cu
’
a chu tr`ınh Hamilton
C
cu
’
a
G
l`a c´ac ca
.
nh cu
’
a
n
gi´ac dˆe
`
u d˜a

cho (H`ınh 4).
Ta c´o bˆo
’
dˆe
`
sau dˆay:
224
V
˜
U D
`
INH H
`
OA, D
ˆ
O
˜
NHU
.
AN
Bˆo
’
dˆe
`
7. Khi
n
ch˘a
˜
n th`ı c´ac dı
’

nh cu
’
a c´ac dˆay cung dˆo
.
d`ai 2 sinh ra mˆo
.
t dˆo
`
thi
.
con dˆa
`
y du
’
K
n
2
, c´ac dı
’
nh c`on la
.
i sinh ra dˆo
`
thi
.
¯
K
n
2
(l`a dˆo

`
thi
.
c´o
n
2
dı
’
nh v`a khˆong c´o ca
.
nh n`ao ca
’
).
Ch´u
.
ng minh. Theo Bˆo
’
dˆe
`
6 th`ı c´o d´ung
n
2
dˆay cung dˆo
.
d`ai 2. Theo Bˆo
’
dˆe
`
2 th`ı c´ac dˆay
cung n`ay ta

.
o th`anh mˆo
.
t
da gi´ac dˆe
`
u
n
2
ca
.
nh. Ta d´anh sˆo
´
c´ac dı
’
nh cu
’
a da gi´ac dˆe
`
u
n
2
ca
.
nh
n`ay bo
.
’
i
A

1
, A
2
, . . . , A
n
2
v`a c´ac dı
’
nh c`on la
.
i cu
’
a dˆo
`
thi
.
G
l`a
B
1
, B
2
, . . . , B
n
2
nhu
.
trong h`ınh 4.
A
1

B
1
1
2
−
n
A
2
n
A
2
n
B
1
2
−
n
B
B
2
A
2
A
1
B
1
1
2
−
n

A
2
n
A
2
n
B
1
2
−
n
B
B
2
A
2
H`ınh 4. C´ac dı
’
nh
A
1
, A
2
, , A
n/2
cu
’
a c´ac dˆay cung dˆo
.
d`ai 2 sinh ra dˆo

`
thi
.
dˆa
`
y du
’
K
n/2
Bˆay gi`o
.
ta ch´u
.
ng to
’
r˘a
`
ng c´ac dˆay
dˆo
.
d`ai ch˘a
˜
n

chı
’
nˆo
´
i c´ac dı
’

nh cu
’
a tˆa
.
p
{A
1
, A
2
, . . . , A
n
2
}
v´o
.
i nhau. Thˆa
.
t vˆa
.
y, gia
’
su
.
’
ngu
.
o
.
.
c la

.
i l`a tˆo
`
n ta
.
i mˆo
.
t dˆay
dˆo
.
d`ai ch˘a
˜
n

nˆo
´
i hai dı
’
nh
B
i
v`a
B
j
cu
’
a
{B
1
, B

2
, . . . , B
n
2
}
v´o
.
i nhau. X´et hai tru
.
`o
.
ng ho
.
.
p:
a) Sˆo
´
ch˘a
˜
n
 =
n
2
.
Theo Bˆo
’
dˆe
`
2, th`ı c´ac dˆay
(A

i−1
, A
j−1
)
v`a
(A
i
, A
j
)
khˆong pha
’
i l`a ca
.
nh cu
’
a dˆo
`
thi
.
G
. Suy
rˆo
.
ng ra, nˆe
´
u c´o
0 < x <
n
2

(
x 
n
2
theo Bˆo
’
dˆe
`
6) dˆay cung dˆo
.
d`ai

nˆo
´
i c´ac dı
’
nh cu
’
a tˆa
.
p ho
.
.
p
{B
1
, B
2
, . . . , B
n

2
}
v´o
.
i nhau, th`ı c´o ´ıt nhˆa
´
t
x + 1
dˆay cung dˆo
.
d`ai ch˘a
˜
n c´o hai dı
’
nh c`ung thuˆo
.
c
{A
1
, A
2
, . . . , A
n
2
}
khˆong pha
’
i l`a ca
.
nh cu

’
a dˆo
`
thi
.
G
. T`u
.
d´o suy ra l`a c´o khˆong qu´a
n
2
− (x+ 1)
dˆay cung dˆo
.
d`ai

nˆo
´
i hai dı
’
nh cu
’
a tˆa
.
p ho
.
.
p
{A
1

, A
2
, . . . , A
n
2
}
. Khi d´o tˆo
’
ng sˆo
´
dˆay cung dˆo
.
d`ai

s˜e khˆong vu
.
o
.
.
t qu´a
x +
n
2
− (x + 1) =
n
2
− 1
l`a diˆe
`
u mˆau thuˆa

˜
n v´o
.
i Bˆo
’
dˆe
`
6. Do d´o pha
’
i
c´o
x =
n
2
. L´uc n`ay chu tr`ınh:
C

= (B
1
A
1
A
n
2
B
n
2
A
n
2

−1
. . . A
n
2
+2−

2
A
n
2
+1−

2
B
n
2
+2−

2
B
2
A
2
B
3
A
3
. . . B
n
2

+1−

2
)
l`a mˆo
.
t chu tr`ınh Hamilton th´u
.
hai cu
’
a
G
, mˆau thuˆa
˜
n v´o
.
i gia
’
thiˆe
´
t l`a
C
l`a chu tr`ınh Hamilton
duy nhˆa
´
t cu
’
a
G
.

b) Sˆo
´
ch˘a
˜
n
 =
n
2
.
Theo Bˆo
’
dˆe
`
2, th`ı c´ac dˆay
(A
i−1
, A
j−1
)
v`a
(A
i
, A
j
)
khˆong pha
’
i l`a ca
.
nh cu

’
a dˆo
`
thi
.
G
. Suy
rˆo
.
ng ra, nˆe
´
u c´o
0 < x <
n
4
(
x 
n
4
theo Bˆo
’
dˆe
`
6) dˆay cung dˆo
.
d`ai

nˆo
´
i c´ac dı

’
nh cu
’
a tˆa
.
p ho
.
.
p
{B
1
, B
2
, . . . , B
n
2
}
v´o
.
i nhau, th`ı c´o ´ıt nhˆa
´
t
x + 1
dˆay cung dˆo
.
d`ai ch˘a
˜
n c´o hai dı
’
nh c`ung thuˆo

.
c
{A
1
, A
2
, . . . , A
n
2
}
khˆong pha
’
i l`a ca
.
nh cu
’
a dˆo
`
thi
.
G
. T`u
.
d´o suy ra l`a c´o khˆong qu´a
n
4
− (x +1)
dˆay cung dˆo
.
d`ai


nˆo
´
i hai dı
’
nh cu
’
a tˆa
.
p ho
.
.
p
{A
1
, A
2
, . . . , A
n
2
}
. Khi d´o tˆo
’
ng sˆo
´
dˆay cung dˆo
.
d`ai

s˜e khˆong vu

.
o
.
.
t qu´a
x +
n
4
− (x + 1) =
n
4
− 1
l`a diˆe
`
u mˆau thuˆa
˜
n v´o
.
i Bˆo
’
dˆe
`
6. Do d´o pha
’
i
c´o
x =
n
4
. L´uc n`ay chu tr`ınh:

C

= (B
1
A
1
A
n
2
B
n
2
A
n
2
−1
. . . A
n
4
+2
A
n
4
+1
B
n
4
+2
B
2

A
2
B
3
A
3
. . . B
n
4
+1
)
S
ˆ
O
´
D
ˆ
O
`
THI
.
HAMILTON T
ˆ
O
´
I DA
.
I
225
l`a mˆo

.
t chu tr`ınh Hamilton th´u
.
hai cu
’
a
G
, mˆau thuˆa
˜
n v´o
.
i gia
’
thiˆe
´
t
C
l`a chu tr`ınh Hamilton
duy nhˆa
´
t cu
’
a
G
.
T´om la
.
i, khˆong c´o dˆay cung
dˆo
.

d`ai ch˘a
˜
n n`ao nˆo
´
i hai dı
’
nh cu
’
a tˆa
.
p ho
.
.
p
{B
1
, B
2
, . . . , B
n
2
}
v´o
.
i nhau. Do
d´o c´ac dı
’
nh cu
’
a

{B
1
, B
2
, . . . , B
n
2
}
sinh ra dˆo
`
thi
.
¯
K
n
2
. C´ac dˆay cung dˆo
.
d`ai
ch˘a
˜
n chı
’
nˆo
´
i c´ac
dı
’
nh cu
’

a tˆa
.
p ho
.
.
p
A
1
, A
2
, . . . , A
n
2
v´o
.
i nhau. T`u
.
Bˆo
’
dˆe
`
6 dˆe
˜
d`ang suy ra c´ac
dı
’
nh cu
’
a
A

1
, A
2
, . . . , A
n
2
l`a dı
’
nh cu
’
a mˆo
.
t dˆo
`
thi
.
dˆa
`
y du
’
n
2
dı
’
nh. Bˆo
’
dˆe
`
du
.

o
.
.
c ch´u
.
ng minh.

Ta go
.
i mˆo
.
t dı
’
nh cu
’
a
G
l`a dı
’
nh dˆa
`
y du
’
nˆe
´
u n´o du
.
o
.
.

c nˆo
´
i v´o
.
i tˆa
´
t ca
’
c´ac
dı
’
nh kh´ac cu
’
a dˆo
`
thi
.
. Ta
di
.
nh ngh˜ıa khoa
’
ng c´ach gi˜u
.
a hai
dı
’
nh cu
’
a

G
l`a dˆo
.
d`ai con du
.
`o
.
ng ng˘a
´
n nhˆa
´
t do
.
c theo
chu tr`ınh Hamilton
C
nˆo
´
i ch´ung v´o
.
i nhau. Nhu
.
vˆa
.
y
dˆo
.
d`ai cu
’
a mˆo

.
t dˆay cung ch´ınh l`a khoa
’
ng
c´ach gi˜u
.
a hai
dı
’
nh cu
’
a n´o. Sau dˆay ta nghiˆen c´u
.
u c´ac dˆay cung c´o
dˆo
.
d`ai 3.
A
1
A
2
A
3
A
n
A
n-1
A
n-2
A

1
A
2
A
3
A
n
A
n-1
A
n-2
H`ınh 5. Chu tr`ınh Hamilton m´o
.
i ta
.
o bo
.
’
i c´ac dˆay cung
dˆo
.
d`ai 3
Hai dˆay cung
dˆo
.
d`ai 3 du
.
o
.
.

c xem l`a c´ach nhau khoa
’
ng c´ach 2 theo chiˆe
`
u kim
dˆo
`
ng hˆo
`
(ho˘a
.
c chiˆe
`
u ngu
.
o
.
.
c kim
dˆo
`
ng hˆo
`
) nˆe
´
u 2 dı
’
nh xuˆa
´
t ph´at cu

’
a n´o t´ınh theo chiˆe
`
u quy di
.
nh c´ach
nhau
dˆo
.
d`ai 2. Ta go
.
i mˆo
.
t dı
’
nh l`a dı
’
nh tu
.
.
do nˆe
´
u n´o khˆong l`a
dı
’
nh cu
’
a dˆay cung dˆo
.
d`ai 3

n`ao ca
’
, v`a mˆo
.
t dı
’
nh l`a dı
’
nh de
.
p nˆe
´
u t`u
.
n´o c´o hai dˆay cung
dˆo
.
d`ai 3 xuˆa
´
t ph´at. Ta c´o bˆo
’
dˆe
`
tiˆe
´
p theo sau
dˆay:
Bˆo
’
dˆe

`
8. Nˆe
´
u sˆo
´
dı
’
nh
n
cu
’
a dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i
G
l`a sˆo
´
le
’
th`ı
G
c´o hai dı
’
nh tu

.
.
do l`a
l´ang giˆe
`
ng cu
’
a c`ung mˆo
.
t
dı
’
nh de
.
p trˆen chu tr`ınh Hamilton cu
’
a
G
. Nˆe
´
u sˆo
´
dı
’
nh
n
cu
’
a dˆo
`

thi
.
Hamilton tˆo
´
i
da
.
i
G
l`a sˆo
´
ch˘a
˜
n th`ı
G
c´o 2 dı
’
nh de
.
p c´o khoa
’
ng c´ach le
’
t´o
.
i nhau v`a 4
dı
’
nh tu
.

.
do l`a l´ang giˆe
`
ng cu
’
a hai
dı
’
nh de
.
p n`ay o
.
’
trˆen chu tr`ınh Hamilton.
Ch´u
.
ng minh. Khi
n
le
’
th`ı theo Bˆo
’
dˆe
`
6 dˆo
`
thi
.
G
c´o d´ung

n−1
2
dˆay cung dˆo
.
d`ai 3. Theo Bˆo
’
dˆe
`
2 ch´ung khˆong thˆe
’
c´o khoa
’
ng c´ach 1 t´o
.
i nhau, mˆo
˜
i dˆay cung
dˆo
.
d`ai 3 c´o khoa
’
ng c´ach 2 t´o
.
i
dˆay cung tiˆe
´
p theo m`a thˆoi. Nˆe
´
u b˘a
´

t
dˆa
`
u t`u
.
mˆo
.
t dˆay cung
dˆo
.
d`ai 3 ke
’
c´ac dˆay cung dˆo
.
d`ai
3 tiˆe
´
p theo theo quy t˘a
´
c c´u
.
dˆay tiˆe
´
p theo c´ach dˆay tru
.
´o
.
c n´o
dˆo
.

d`ai 3 theo chiˆe
`
u ngu
.
o
.
.
c kim
dˆo
`
ng hˆo
`
th`ı dˆay dˆa
`
u tiˆen v`a dˆay th´u
.
n−1
2
c´o dı
’
nh chung. Ta dˆe
˜
t´ınh du
.
o
.
.
c l`a nˆe
´
u dˆay

dˆo
.
d`ai
3
dˆa
`
u tiˆen b˘a
´
t dˆa
`
u v´o
.
i
dı
’
nh th´u
.
nhˆa
´
t, th`ı dˆay th´u
.
n−1
2
c´o dı
’
nh cuˆo
´
i l`a dı
’
nh th´u

.
(1 + 2 ×
n − 3
2
) + 3 = 1( mod n)
T´u
.
c l`a
G
luˆon c´o mˆo
.
t dı
’
nh de
.
p
v
. L´ang giˆe
`
ng cu
’
a dı
’
nh de
.
p
v
n`ay theo Bˆo
’
dˆe

`
2 chı
’
c´o thˆe
’
l`a
226
V
˜
U D
`
INH H
`
OA, D
ˆ
O
˜
NHU
.
AN
dı
’
nh tu
.
.
do, t´u
.
c l`a hai l´ang giˆe
`
ng cu

’
a
v
l`a hai dı
’
nh tu
.
.
do trong
G
.
Khi
n
l`a sˆo
´
le
’
th`ı
G
c´o
n
2
− 1
dˆay cung dˆo
.
d`ai 3. Ta kh˘a
’
ng di
.
nh r˘a

`
ng
G
c´o ´ıt nhˆa
´
t mˆo
.
t dı
’
nh
de
.
p, v`ı nˆe
´
u
G
khˆong c´o dı
’
nh de
.
p n`ao, th`ı mˆo
˜
i dˆay cung c´o dˆo
.
d`ai 2 t´o
.
i dˆay cung tiˆe
´
p theo v`a
du

.
o
.
.
c bˆo
´
tr´ı nhu
.
trong H`ınh 5, khi
d´o dˆe
˜
thˆa
´
y c´ac ca
.
nh du
.
o
.
.
c tˆo
dˆa
.
m ta
.
o th`anh mˆo
.
t chu tr`ınh
Hamilton m´o
.

i (trong H`ınh 5, c´ac ca
.
nh cu
’
a ch´ung
du
.
o
.
.
c tˆo
dˆa
.
m n´et):
C

= (A
1
A
2
A
3
. . . A
4k+2
A
4k+3
. . . A
n−2
A
n−1

A
n
. . . A
4k+1
A
4k
. . . A
5
A
4
),
mˆau thuˆa
˜
n v´o
.
i gia
’
thiˆe
´
t
C
l`a chu tr`ınh Hamilton duy nhˆa
´
t cu
’
a
G
. Mˆau thuˆa
˜
n d´o ch´u

.
ng to
’
r˘a
`
ng
G
pha
’
i c´o dı
’
nh de
.
p
v
. T´ınh t`u
.
dı
’
nh
v
n`ay theo chiˆe
`
u ngu
.
o
.
.
c kim
dˆo

`
ng hˆo
`
v`a chiˆe
`
u kim
dˆo
`
ng hˆo
`
,
n
2
− 1
dˆay cung dˆo
.
d`ai 3 liˆen tiˆe
´
p nhau s˜e c´ach nhau dˆo
.
d`ai 2, v`a s˜e cho ta mˆo
.
t dı
’
nh
de
.
p
u
th´u

.
hai (xem H`ınh 6). Thˆa
.
t vˆa
.
y, vi
.
tr´ı cu
’
a
u
c´o thˆe
’
t´ınh du
.
o
.
.
c
do
.
n gia
’
n nˆe
´
u nhu
.
d´anh
sˆo
´

c´ac dı
’
nh cu
’
a
G
l`a
A
1
, A
2
, . . . A
n
ngu
.
o
.
.
c chiˆe
`
u kim
dˆo
`
ng hˆo
`
v`a gia
’
su
.
’

v = A
1
v`a c´o
k
dˆay
cung
dˆo
.
d`ai 3 liˆen tiˆe
´
p nhau theo chiˆe
`
u ngu
.
o
.
.
c kim
dˆo
`
ng hˆo
`
v`a
n
2
− 1 − k
dˆay cung dˆo
.
d`ai
3 theo chiˆe

`
u kim
dˆo
`
ng hˆo
`
t´ınh t`u
.
v
. Dı
’
nh
u
s˜e l`a dı
’
nh th´u
.
1 + 2(k − 1) + 3 = 2k + 4
, d´o
c˜ung l`a
dı
’
nh cuˆo
´
i cu
’
a dˆay th´u
.
n
2

− 1 − k
t´ınh t`u
.
v
theo chiˆe
`
u kim dˆo
`
ng hˆo
`
theo cˆong th´u
.
c
n − 2((
n
2
− 1 − k) − 1) = 2k + 4
(mod
n
). L´uc n`ay, tu
.
o
.
ng tu
.
.
nhu
.
tru
.

`o
.
ng ho
.
.
p
n
le
’
, c´ac l´ang
giˆe
`
ng cu
’
a
u
v`a
v
trˆen
C
s˜e l`a c´ac dı
’
nh tu
.
.
do, v`a ch´ung ta dˆe
˜
thˆa
´
y l´ang giˆe

`
ng cu
’
a
u
c´o khoa
’
ng
c´ach le
’
t´o
.
i l´ang giˆe
`
ng cu
’
a
v
. Bˆo
’
dˆe
`
du
.
o
.
.
c ch´u
.
ng minh.


v = A
1
A
n
A
n-1
A
n-2
A
2
A
3
u = A
2k+4
v = A
1
A
n
A
n-1
A
n-2
A
2
A
3
u = A
2k+4
H`ınh 6. Hai dı

’
nh de
.
p
v
v`a
u
khi
n
ch˘a
˜
n.
Bˆo
’
dˆe
`
9. Dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i luˆon c´o duy nhˆa
´
t mˆo
.
t dı
’

nh dˆa
`
y du
’
m`a hai l´ang giˆe
`
ng cu
’
a
n´o trˆen chu tr`ınh Hamilton l`a
dı
’
nh bˆa
.
c 2.
Ch´u
.
ng minh. Dˆe
˜
thˆa
´
y, nˆe
´
u
dˆo
`
thi
.
Hamilton tˆo
´

i da
.
i c´o 2 dı
’
nh dˆa
`
y du
’
th`ı n´o c´o nhiˆe
`
u ho
.
n mˆo
.
t
chu tr`ınh Hamilton. Bˆay gi`o
.
, ta ch´u
.
ng minh r˘a
`
ng c´ac
dı
’
nh l´ang giˆe
`
ng
A
2
v`a

A
n
cu
’
a dı
’
nh de
.
p
v = A
1
luˆon l`a dı
’
nh bˆa
.
c 2. Khi d´o dˆe
˜
thˆa
´
y r˘a
`
ng dı
’
nh de
.
p
A
1
l`a dı
’

nh dˆa
`
y du
’
. Thˆa
.
t vˆa
.
y, nˆe
´
u
c´o mˆo
.
t chu tr`ınh Hamilton n`ao
d´o cu
’
a dˆo
`
thi
.
G
th`ı do c´ac dı
’
nh
A
2
v`a
A
n
c´o bˆa

.
c l`a 2 nˆen
dı
’
nh
A
1
luˆon l`a dı
’
nh kˆe
`
v´o
.
i
A
2
v`a
A
n
trˆen chu tr`ınh Hamilton n`ay, do d´o viˆe
.
c bˆo
’
sung ca
.
nh
nˆo
´
i
A

1
v´o
.
i tˆa
´
t ca
’
c´ac
dı
’
nh kh´ac cu
’
a
G
khˆong l`am dˆo
`
thi
.
c´o thˆem chu tr`ınh Hamilton nˆe
´
u ban
dˆa
`
u n´o chı
’
c´o duy nhˆa
´
t mˆo
.
t chu tr`ınh Hamilton. Do diˆe

`
u kiˆe
.
n tˆo
´
i da
.
i cu
’
a
G
(dˆo
`
thi
.
nhiˆe
`
u
ca
.
nh nhˆa
´
t trong c´ac
dˆo
`
thi
.
c´o c`ung sˆo
´
dı

’
nh v`a c´o duy nhˆa
´
t mˆo
.
t chu tr`ınh Hamilton) th`ı
A
1
pha
’
i l`a dı
’
nh dˆa
`
y du
’
trong dˆo
`
thi
.
G
.
S
ˆ
O
´
D
ˆ
O
`

THI
.
HAMILTON T
ˆ
O
´
I DA
.
I
227
Dˆe
’
ch´u
.
ng minh bˆo
’
dˆe
`
, ta gia
’
su
.
’
ngo
.
.
c la
.
i l`a t`u
.

A
2
c´o dˆay cung
e
xuˆa
´
t ph´at. Ta x´et hai
tru
.
`o
.
ng ho
.
.
p
n
ch˘a
˜
n v`a
n
le
’
v`a thu du
.
o
.
.
c mˆo
.
t mˆau thuˆa

˜
n thˆong qua viˆe
.
c xˆay du
.
.
ng mˆo
.
t chu
tr`ınh Hamilton th´u
.
hai b˘a
`
ng c´ach su
.
’
du
.
ng c´ac dˆay cung
dˆo
.
d`ai 3 cu
’
a dˆo
`
thi
.
G
:
a) Tru

.
`o
.
ng ho
.
.
p
n
l`a sˆo
´
le
’
:
Trong h`ınh 7, ta c´o thˆe
’
xˆay du
.
.
ng
du
.
o
.
.
c c´ac chu tr`ınh Hamilton tu
.
o
.
ng ´u
.

ng v´o
.
i tru
.
`o
.
ng ho
.
.
p
dˆo
.
d`ai cu
’
a
e
l`a le
’
tu
.
o
.
ng ´u
.
ng h`ınh bˆen tr´ai v`a tu
.
o
.
ng ´u
.

ng v´o
.
i
dˆo
.
d`ai
e
ch˘a
˜
n l`a h`ınh bˆen pha
’
i
cu
’
a H`ınh 7.
A
1
A
n
A
n-1
A
n-2
A
2
A
2k+1
A
2k+4
A

2k
A
2k-1
A
1
A
n
A
2
A
2k+1
A
2k+4
A
2k
A
2k-1
A
2k+2
A
1
A
n
A
n-1
A
n-2
A
2
A

2k+1
A
2k+4
A
2k
A
2k-1
A
1
A
n
A
2
A
2k+1
A
2k+4
A
2k
A
2k-1
A
2k+2
H`ınh 7. Chu tr`ınh Hamilton du
.
o
.
.
c ta
.

o du
.
.
ng khi
n
le
’
v=A
1
A
n
A
n-1
A
2
A
2k+1
u = A
2k+4
A
3
v=A
1
A
n
A
n-1
A
2
A

3
A
2k+1
u = A
2k+4
v=A
1
A
n
A
n-1
A
2
A
2k+1
u = A
2k+4
A
3
v=A
1
A
n
A
n-1
A
2
A
3
A

2k+1
u = A
2k+4
H`ınh 8. Chu tr`ınh Hamilton du
.
o
.
.
c ta
.
o du
.
.
ng khi
n
ch˘a
˜
n
b) Tru
.
`o
.
ng ho
.
.
p
n
l`a sˆo
´
ch˘a

˜
n:
Theo Bˆo
’
dˆe
`
7, c´o
n
2
dı
’
nh khˆong kˆe
`
nhau trˆen chu tr`ınh Hamilton sinh mˆo
.
t dˆo
`
thi
.
con dˆa
`
y
du
’
v`a
n
2
dı
’
nh c`on la

.
i sinh mˆo
.
t dˆo
`
thi
.
khˆong c´o ca
.
nh n`ao ca
’
. Theo Bˆo
’
dˆe
`
8 th`ı hai dı
’
nh de
.
p
cu
’
a
G
c´ach nhau mˆo
.
t khoa
’
ng c´ach le
’

, nˆen c´o mˆo
.
t trong ch´ung l`a dı
’
nh cu
’
a dˆo
`
thi
.
con dˆa
`
y du
’
K
n
2
. Khˆong mˆa
´
t tˆo
’
ng qu´at gia
’
su
.
’
A
1
l`a dı
’

nh cu
’
a dˆo
`
thi
.
con dˆa
`
y du
’
K
n
2
, khi d´o l´ang giˆe
`
ng
A
2
cu
’
a n´o chı
’
c´o thˆe
’
c´o dˆay cung nˆo
´
i t´o
.
i
dı

’
nh c´o chı
’
sˆo
´
le
’
A
2x+1
n`ao d´o cu
’
a dˆo
`
thi
.
dˆa
`
y du
’
K
n
2
.
Gia
’
su
.
’
dı
’

nh de
.
p th´u
.
hai l`a
u = A
2k+4
nhu
.
trong ch´u
.
ng minh cu
’
a Bˆo
’
dˆe
`
8. Trong tru
.
`o
.
ng ho
.
.
p
n`ay, ta xˆay du
.
.
ng chu tr`ınh Hamilton th´u
.

hai nhu
.
bˆen tr´ai cu
’
a H`ınh 8 nˆe
´
u dˆay cung
e
khˆong
phˆan c´ach hai
dı
’
nh de
.
p v`a bˆen pha
’
i cu
’
a H`ınh 8 nˆe
´
u dˆay cung
e
phˆan c´ach hai dı
’
nh de
.
p n`ay.
Nhu
.
vˆa

.
y trong ca
’
hai tru
.
`o
.
ng ho
.
.
p a) v`a b) ta
dˆe
`
u thu du
.
o
.
.
c mˆo
.
t chu tr`ınh Hamilton th´u
.
hai,
diˆe
`
u n`ay mˆau thuˆa
˜
n v´o
.
i gia

’
thiˆe
´
t l`a
G
chı
’
c´o duy nhˆa
´
t mˆo
.
t chu tr`ınh Hamilton. Mˆau
thuˆa
˜
n n`ay ch´u
.
ng to
’
r˘a
`
ng
dı
’
nh
A
2
v`a tu
.
o
.

ng tu
.
.
dı
’
nh
A
n
khˆong c´o dˆay cung n`ao xuˆa
´
t ph´at ca
’
ngo`ai c´ac ca
.
nh cu
’
a chu tr`ınh Hamilton cu
’
a
G
. Nhu
.
vˆa
.
y c´ac
dı
’
nh n`ay c´o bˆa
.
c l`a 2, v`a do d´o

228
V
˜
U D
`
INH H
`
OA, D
ˆ
O
˜
NHU
.
AN
dı
’
nh
A
1
l`a dı
’
nh dˆa
`
y du
’
.

4. CH
´
U

.
NG MINH
DI
.
NH L
´
Y 3
Ta ch´u
.
ng minh kˆe
´
t luˆa
.
n ma
.
nh ho
.
n cu
’
a
Di
.
nh l´y 3, r˘a
`
ng mˆo
˜
i mˆo
.
t dˆo
`

thi
.
Hamilton tˆo
´
i da
.
i
n  3
dı
’
nh d˘a
’
ng cˆa
´
u v´o
.
i mˆo
.
t
dˆo
`
thi
.
du
.
o
.
.
c xˆay du
.

.
ng bo
.
’
i thuˆa
.
t to´an nˆeu trong
Di
.
nh l´y 2. K´y
hiˆe
.
u thuˆa
.
t to´an n`ay l`a
Φ
. Dˆe
˜
kiˆe
’
m tra thˆa
´
y kˆe
´
t luˆa
.
n cu
’
a Di
.

nh l´y 3 d´ung cho tru
.
`o
.
ng ho
.
.
p
n = 3
v`a
n = 4
. Gia
’
su
.
’
kˆe
´
t luˆa
.
n cu
’
a
Di
.
nh l´y 3 d´ung cho
n ≥ 7
r˘a
`
ng mˆo

˜
i mˆo
.
t dˆo
`
thi
.
Hamilton
tˆo
´
i
da
.
i
n ≥ 7
dı
’
nh d˘a
’
ng cˆa
´
u v´o
.
i mˆo
.
t
dˆo
`
thi
.

du
.
o
.
.
c xˆay du
.
.
ng bo
.
’
i thuˆa
.
t to´an
Φ
. Ta ch´u
.
ng minh
kˆe
´
t luˆa
.
n cu
’
a
di
.
nh l´y c˜ung d´ung cho mo
.
i dˆo

`
thi
.
Hamilton tˆo
´
i da
.
i
n + 1
dı
’
nh. Thˆa
.
t vˆa
.
y x´et
G
l`a dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i
n + 1
dı
’
nh. Theo Di

.
nh l´y 1 th`ı dˆo
`
thi
.
G
c´o
[
(n+1)
2
4
] + 1
ca
.
nh.
Theo Bˆo
’
dˆe
`
9, dˆo
`
thi
.
G
c´o mˆo
.
t dı
’
nh dˆa
`

y du
’
, k´y hiˆe
.
u l`a
A
n+1
v´o
.
i hai l´ang giˆe
`
ng
A
1
v`a
A
n
c´o bˆa
.
c l`a 2. Ta d´anh sˆo
´
c´ac dı
’
nh cu
’
a
G
bo
.
’

i
A
1
, A
2
, . . . , A
n+1
theo chiˆe
`
u ngu
.
.
c kim
dˆo
`
ng hˆo
`
do
.
c theo chu tr`ınh Hamilton cu
’
a n´o. Ta x´et
dˆo
`
thi
.
m´o
.
i ta
.

o th`anh
G

thu du
.
o
.
.
c t`u
.
G
b˘a
`
ng
c´ach bo
’
di c´ac dı
’
nh
A
1
, A
n
, A
n+1
v`a thˆem v`ao dı
’
nh
A


1
v`a ´ac ca
.
nh nˆo
´
i
A

1
v´o
.
i
dı
’
nh
A
2
v`a
dı
’
nh
A
n−1
. Dˆe
˜
thˆa
´
y r˘a
`
ng dˆo

`
thi
.
thu du
.
o
.
.
c
G

c˜ung chı
’
c´o mˆo
.
t chu tr`ınh Hamilton duy nhˆa
´
t
C

= (A

1
A
2
. . . A
n−1
A

1

)
m`a thˆoi. Thˆa
.
t vˆa
.
y, gia
’
su
.
’
ngu
.
.
c la
.
i l`a
G

c´o mˆo
.
t chu tr`ınh Hamilton
th´u
.
hai
C
∗
= (A

1
A


2
. . . A
n−1
A

1
)
, th`ı dˆo
`
thi
.
G
c´o chu tr`ınh Hamilton th´u
.
hai thu t`u
.
C
∗
b˘a
`
ng
c´ach thay thˆe
´
dı
’
nh
A

1

bo
.
’
i d˜ay
dı
’
nh
A
1
A
n+1
A
n
l`a diˆe
`
u vˆo l´y. M˘a
.
t kh´ac dˆo
`
thi
.
G

c´o d´ung
[
(n+1)
2
4
] + 1 − n = [
(n−1)

2
4
] + 1
ca
.
nh, nˆen
G

c˜ung l`a dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i
n − 1
dı
’
nh. Theo
gia
’
thiˆe
´
t quy na
.
p th`ı
G


thu du
.
o
.
.
c b˘a
`
ng c´ach ´ap du
.
ng thuˆa
.
t to´an
Φ
. Lu
.
u ´y r˘a
`
ng, mˆo
˜
i
dˆo
`
thi
.
thu
du
.
o
.
.

c b˘a
`
ng c´ach ´ap du
.
ng thuˆa
.
t to´an
Φ
dˆe
`
u c´o d´ung hai dı
’
nh bˆa
.
c 2, l`a hai dı
’
nh kˆe
`
cu
’
a
dı
’
nh dˆa
`
y du
’
du
.
o

.
.
c ta
.
o du
.
.
ng trong thuˆa
.
t to´an. Nhu
.
vˆa
.
y, dˆe
˜
thˆa
´
y
dˆo
`
thi
.
G
thu du
.
o
.
.
c b˘a
`

ng c´ach
´ap du
.
ng thuˆa
.
t to´an
Φ
v´o
.
i
dı
’
nh dˆa
`
y du
’
dˆa
`
u tiˆen
A
n+1
v`a sau d´o tiˆe
´
p tu
.
c ´ap du
.
ng thuˆa
.
t to´an

Φ
. Nhu
.
vˆa
.
y kˆe
´
t luˆa
.
n cu
’
a
di
.
nh l´y c˜ung d´ung cho c´ac dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i
n + 1
dı
’
nh. Vˆa
.
y
di

.
nh l´y du
.
o
.
.
c ch´u
.
ng minh.

T
`
AI LI
ˆ
E
.
U THAM KHA
’
O
[1] C. A. Barefoot, R. C. Entringer, Extremal maximal uniquely Hamiltonian, J. Graph The-
ory 4 (1980) 93—100.
[2] J. A. Bondy, B. Jackson, Vertices of small degree in uniquely Hamiltonian graphs,
(1997).
[3] M. Aigner, Graphentheorie, Teubner, Stuttgart, 1984.
[4] P.Erdos, Remark on a paper of p´osa, Publ. Math. Inst. Hungary. Acad. Sci. VII (1962)
227—229.
[5] V˜u
D`ınh H`oa, Dˆo
˜
Nhu

.
An, Kˆe
´
t qua
’
m´o
.
i vˆe
`
dˆo
`
thi
.
Hamilton tˆo
´
i da
.
i, Ta
.
p ch´ı Tin ho
.
c v`a
Diˆe
`
u khiˆe
’
n ho
.
c 22 (2006) 117—122.
[6] J. Sheehan, Graphs with exactly one Hamiltonian circuit, J. Graph Theory 1 (1977)

37—43.
Nhˆa
.
n b`ai ng`ay 17 - 8 - 2006