Dacă oricare două vîrfuri x, yÎV sînt unite printr-un lanţ simplu unic, atunci orice muchie [x, y]ÎU reprezintă unicul lanţ dintre x şi y. Suprimînd muchia [x, y], între x şi y nu va mai exista lanţ, deci graful obţinut nu va mai fi conex.
3 Þ 4
Notăm cu n numărul de vîrfuri şi cu m numărul de muchii din graf.
Pentru a demonstra că orice graf conex minimal are n-1 muchii vom demonstra prin inducţie completă după n că m £ n-1. Cum în orice graf conex m ³ n-1, deducem m = n-1.
P(1) Dacă n = 1, atunci m = 0 Þ m = n-1.
P(2) Dacă n = 2, atunci m =1 Þ m = n-1.
P(n) Presupunem că într-un graf conex minimal cu cel mult n vîrfuri numărul de muchii este strict mai mic decît numărul de vîrfuri.
P(n+1) Demonstrăm că într-un graf conex minimal cu n+1 vîrfuri, numărul de muchii este cel mult egal cu n.
Fie G conex minimal cu n+1 vîrfuri şi m muchii. Eliminînd o muchie oarecare din graf obţinem un graf G’ cu m-1 muchii şi două componente conexe C1 şi C2 cu n1, respectiv n2 vîrfuri (n1+n2 = n+1) şi m1, respectiv m2 muchii (m1+m2 = m-1). Subgrafurile C1 şi C2 sînt conexe minimale, altfel graful G nu ar fi conex minimal. Din ipoteza inductivă rezultă că m1 £ n1-1, m2 £ n2-1; dar m1+m2 = m-1 £ n1+n2 = n-2 Þ m £ n-1. Deci G conex minimal implică G conex cu n-1 muchii.
4 Þ 5
Fie G un graf conex cu n-1 muchii. Să demonstrăm că G este aciclic.
Presupunem prin reducere la absurd, că graful G conţine un ciclu C format din vîrfurile v1, v2, …, vk.
Să considerăm subgraful parţial Gk = (Vk, Uk) constînd din ciclul C. Deci Vk = {v1, v2 ,…, vk}, iar Uk = {[v1,v2)], [v2,v3],…,[vk-1,vk], (vk,v1]} (½Vk½=½Uk½= k). Dacă ½Vk½<½V½, atunci $viÎVk şi vk+1ÎV-Vk astfel încît [vi, vk+1]ÎU, graful G fiind conex.
Construim Gk+1 = (Vk+1, Uk+1) în modul următor: Vk+1 = Vk È{vk+1}; Uk+1=UkÈ{[vi,vk+1]} şi ½Uk+1½=½Vk+1½=k+1.
Cît timp k+1 < n, aplicăm acelaşi procedeu pînă cînd obţinem un graf Gn = (V, Un), cu ½Un½= n, Un Í U; deci ½U½ ³ n, contradicţie cu ipoteza ½U½= n-1.
5 Þ 6
Presupunem că graful G este aciclic cu n-1 muchii, să demonstrăm că G este aciclic maximal.
Fie C1, C2,…, Cp cele p componentele conexe ale grafului G, avînd respectiv n1, n2,…, np vîrfuri şi m1, m2,…, mp muchii fiecare. Evident că n1+n2+…+np = n şi m1+m2+…+mp = n-1.
Cum graful G este aciclic, deducem că fiecare componentă conexă este un arbore. Deoarece am demonstrat că 1 Þ 5, rezultă că m i= ni-1, “iÎ{1, 2, …, p}. Înlocuind în relaţia de mai sus, obţinem n-p = n-1 Þ p = 1, deci G conex. Dacă G este conex şi aciclic, conform definiţiei G este arbore. Dar am demonstrat că 1 Þ 2, deci oricare două vîrfuri din G sînt unite printr-un lanţ simplu. Astfel, adăugînd orice muchie obţinem un ciclu.
6 Þ 1
Presupunem că graful G este aciclic, dar dacă am mai adăuga o muchie s-ar obţine un ciclu. Să demonstrăm că G este conex.
Fie u şi v două vîrfuri neadiacente din graf, arbitrar alese. Deoarece adăugînd muchia [u, v] se obţine un ciclu, rezultă că u şi v sînt unite printr-un lanţ ale cărui muchii aparţin grafului G. Cum u,v au fost alese arbitrar, deducem că graful G este conex.
Q.E.D.
Teorema 2
Numerele întregi 0 < d1 £ d2 £ …£ dn (n ³ 2) sînt gradele vîrfurilor unui arbore dacă şi numai dacă d1+d2+…+dn = 2n-2.
Demonstraţie:
Necesitatea Condiţia este necesară, deoarece orice arbore cu n vîrfuri are n-1 muchii, iar suma gradelor vîrfurilor oricărui graf este de două ori numărul de muchii. Deci d1+d2+…+dn = 2n-2.
Suficienţa Fie 0 < d1 £ d2 £…£ dn astfel încît d1+d2+…+dn = 2n-2.
Să demonstrăm că există un arbore cu gradele vîrfurilor d1, d2,…, dn. Vom proceda prin inducţie.
P(2) Dacă d1+d2 = 2, atunci d1 = d2 = 1 , arborele fiind cel din figura de mai jos:
Fig. 3
P(n) Presupunem acum că proprietatea este adevărată pentru orice secvenţă de n numere naturale 0 < d1 £ d2 £ …£ dn, astfel încît d1+d2+…+dn = 2n-2.
P(n+1) Să demonstrăm că pentru orice secvenţă 0 < d’1 £ d’2 £…£ d’n £ d’n+1 astfel încît d’1+d’2+…+d’n+1 = 2n, există un arbore cu n+1 vîrfuri cu secvenţa gradelor d’1, d’2, …, d’n+1.
Observăm că există măcar un nod terminal x1 cu gradul d’1=1, altfel dacă di ³ 2,”iÎ{1, 2,…, n+1} Þ d’1+d’2+…+d’n+1 ³ 2(n+1), ceea ce contrazice ipoteza. În mod analog, observăm că există măcar un nod neterminal xn+1, cu gradul d’n+1 > 1, altfel dacă d’i = 1,”iÎ{1, 2, …, n+1} Þ d’1+d’2+…+d’n+1 = n+1 < 2n .
Să considerăm următoarea secvenţă de n numere întregi d’2,…, d’n, d’n+1-1 cu proprietatea că d’2+…+d’n+d’n+1 = 2n-2. Din ipoteza inductivă există un arbore An cu n vîrfuri şi secvenţa gradelor d’2,…, d’n, d’n+1-1. Adăugăm la arborele An un vîrf pe care îl unim printr-o muchie cu vîrful avînd gradul d’n+1-1. Obţinem un arbore An+1 cu gradele vîrfurilor d’1, d’2,…, d’n+1.
Q.E.D.
Demonstraţia acestei teoreme oferă şi o soluţie constructivă pentru obţinerea unui arbore cu secvenţa gradelor dată.
Vom reţine gradele vîrfurilor într-un vector d de dimensiune n, ordonat crescător, cu suma componentelor egală cu 2n-2.
Arborele va fi reprezentat prin matricea muchiilor, o matrice a cu două linii şi n-1 coloane, în care pentru fiecare muchie din arbore vom reţine extremităţile.
Spre deosebire de ideea din demonstraţie, pentru a conserva ordinea în vectorul d, la fiecare pas al algoritmului gradul care va fi decrementat va fi primul grad mai mare ca 1 şi nu ultimul.
