Page 36 - MATINF Nr. 9-10

36 C. B˘alc˘au

Demonstrat¸ie. ”⇒” Fie G = (V, E) un graf neorientat simplu cu V = {v 1 , . . . , v n } astfel ˆıncˆat
d G (v i ) = d i , ∀ i ∈ {1, . . . , n}. Deoarece graful G este simplu, adic˘a nu cont , ine nici bucle, nici
muchii multiple, rezult˘ c˘ gradul d n = d G (v n ) este egal cu num˘arul de noduri adiacente cu v n ,
a
a
deci d n ≤ n − 1. Fie M mult , imea nodurilor adiacente cu v n , deci card(M) = d n . Avem dou˘a
cazuri.
0
0
0
, v n−d n+1 , . . . , v n−1 }. Atunci graful G = (V , E ) definit prin
Cazul 1) M = {v n−d n
0
0
V = V \ {v n } = {v 1 , . . . , v n−1 }, E = E \ {[v n , x] | x ∈ M}
este un graf neorientat simplu avˆand gradele nodurilor
d G 0(v i ) = d G (v i ) = d i , pentru 1 ≤ i ≤ n − d n − 1,
0(v i ) = d G (v i ) − 1 = d i − 1, pentru n − d n ≤ i ≤ n − 1,
d G
− 1, d n−d n+1 − 1, . . . , d n−1 − 1) este secvent , ˘ grafic˘a.
a
deci (d 1 , d 2 , . . . , d n−d n−1 , d n−d n
, v n−d n+1 , . . . , v n−1 }. Fie
Cazul 2) M 6= {v n−d n
, v n−d n+1 , . . . , v n−1 }.
A = {v n−d n , v n−d n+1 , . . . , v n−1 } \ M, B = M \ {v n−d n
, v n−d n+1 , . . . , v n−1 }) = card(M) = d n , rezult˘a c˘ avem
a
Cum card ({v n−d n
card(A) = card(B) ≥ 1.

}, unde
Fie r = card(A) = card(B), A = {v j 1 , v j 2 , . . . , v j r } s , i B = {v k 1 , v k 2 , . . . , v k r
{j 1 , j 2 , . . . , j r } ⊆ {n − d n , n − d n + 1, . . . , n − 1} s , i {k 1 , k 2 , . . . , k r } ⊆ {1, 2, . . . , n − d n − 1}.

,
Pentru orice i ∈ {1, 2, . . . , r}, cum d G (v j i ) = d j i ≥ d k i = d G (v k i ) s , i v n nu este adiacent cu v j i
a a a , dar nu este
dar este adiacent cu v k i , rezult˘ c˘ exist˘ un nod v t i ∈ V care este adiacent cu v j i
. Fie graful G 1 = (V, E 1 ) definit prin
adiacent cu v k i
r r

[ [
E 1 = E \ {[v n , v k i ], [v t i , v j i ]} ∪ {[v n , v j i ], [v t i , v k i ]}.
i=1 i=1
Atunci G 1 este un graf neorientat simplu avˆand aceleas , i grade ale nodurilor ca s , i G, adic˘a
ˆ
(v i ) = d G (v i ) = d i , pentru orice i ∈ {1, 2, . . . , n}. In plus, ˆın graful G 1 mult , imea nodurilor
d G 1
, v n−d n+1 , . . . , v n−1 }. Conform demonstrat , iei de la
adiacente cu v n este chiar mult , imea {v n−d n
Cazul 1 (ˆınlocuind G cu G 1 ) rezult˘a din nou c˘
a
− 1, d n−d n+1 − 1, . . . , d n−1 − 1)
(d 1 , d 2 , . . . , d n−d n−1 , d n−d n
este secvent , ˘ grafic˘a.
a
0
0
0
0
”⇐” Fie d n ≤ n − 1 s , i G = (V , E ) un graf neorientat simplu cu V = {v 1 , . . . , v n−1 } astfel
ˆıncˆat
0(v i ) = d i , pentru 1 ≤ i ≤ n − d n − 1,
d G
0(v i ) = d i − 1, pentru n − d n ≤ i ≤ n − 1.
d G
0
0
Atunci graful G = (V, E) definit prin V = V ∪ {v n } = {v 1 , . . . , v n } (cu v n 6∈ V ) s , i
0
E = E ∪ {[v n , v i ] | n − d n ≤ i ≤ n − 1}