Page 34 - MATINF Nr. 9-10

34 C. B˘alc˘au

muchiile multiple e 1 , . . . , e m sunt distincte dou˘a cˆate dou˘a, obt , inem c˘a d G (v 1 ) = m = d 1 s , i
d G (v 2 ) = m = d 2 .

Pentru n ≥ 3 demonstr˘am afirmat , ia prin induct , ie dup˘a m.
Pentru m = 0 rezult˘a c˘a d i = 0, ∀ i ∈ {1, . . . , n}, deci luˆand E = Ø avem d G (v i ) = 0 = d i ,
∀ i ∈ {1, . . . , n}.

∗
Presupunem afirmat , ia adev˘arat˘a pentru m − 1 s , i o demonstr˘am pentru m, unde m ∈ N .
n n−1 n
P P P
Fie d i = 2m, d 1 ≤ d 2 ≤ . . . ≤ d n s , i d n ≤ d i . Deoarece d i = 2m ≥ 2, rezult˘a c˘a d n ≥ 1.
i=1 i=1 i=1
n−1
P
a
Cum d n ≤ d i , rezult˘a c˘ s , i d n−1 ≥ 1. Fie
i=1
ß
d i , dac˘ 1 ≤ i ≤ n − 2,
a
0
d =
i
a
d i − 1, dac˘ i ∈ {n − 1, n}.
n n
P 0 P
Atunci d = d i − 2 = 2(m − 1). Avem dou˘a cazuri.
i
i=1 i=1
n−1 n−1
0
0
0
0
0
Cazul 1) d n−2 < d n . Atunci d ≤ d ≤ . . . ≤ d s , i d = d n − 1 ≤ P d i − 1 = P d , deci,
1 2 n n i
i=1 i=1
0
0
conform ipotezei de induct , ie, exist˘a un multigraf neorientat G = (V, E ) cu V = {v 1 , . . . , v n }
0
0(v i ) = d , ∀ i ∈ {1, . . . , n}.
astfel ˆıncˆat d G i
0
0
0
Cazul 2) d n−2 = d n , deci s , i d n−1 = d n . Atunci d ≤ d ≤ . . . ≤ d 0 = d n s , i d 0 = d =
1 2 n−2 n−1 n
d n − 1, deci
0
max d = d 0 .
i n−2
i=1,n
n n−3 n−3
P 0 0 P P
Avem d − 2d = d i + d n + (d n − 1) + (d n − 1) − 2d n = d i + d n − 2 ≥ −1, deoarece
i n−2
i=1 i=1 i=1
n n
P 0 0 0 P 0 0
d n ≥ 1. Pe de alt˘a parte, d − 2d n−2 = 2(m − 1) − 2d n−2 , deci d − 2d n−2 este un num˘ar
i
i
i=1 i=1
n
P 0 0
a
par. Astfel rezult˘a c˘ d − 2d n−2 ≥ 0. Obt , inem c˘a
i
i=1
n−3
X
0
0
0
max d = d 0 n−2 ≤ d + d 0 n−1 + d ,
n
i
i
i=1,n
i=1
0
0
0
deci, conform ipotezei de induct , ie (aplicat˘ pentru numerele d , d , . . . , d rearanjate ˆın ordine
a
2
1
n
0
0
a
a
a
cresc˘atoare), rezult˘ din nou c˘ exist˘ un multigraf neorientat G = (V, E ) cu V = {v 1 , . . . , v n }
0
0(v i ) = d , ∀ i ∈ {1, . . . , n}.
astfel ˆıncˆat d G i
ˆ 0 0
In ambele cazuri, fie multigraful neorientat G = (V, E ∪ {e}), unde e = [v n−1 , v n ], e 6∈ E .
Evident, avem
0(v n−1 ) + 1 = d 0 + 1 = d n−1 ,
d G (v n−1 ) = d G
n−1
0
0(v n ) + 1 = d + 1 = d n ,
d G (v n ) = d G n
0
d G (v i ) = d G 0(v i ) = d = d i , pentru orice i ∈ {1, . . . , n − 2}.
i
Astfel d G (v i ) = d i , ∀ i ∈ {1, . . . , n}.
Demonstrat , ia prin induct , ie este ˆıncheiat˘a.