1 Cuplaje in grafuri oarecare 2 1.1 Not ,iunipreliminare . . . . . . . . . . . . . . . . . . . . . . [622401]

Contents
1 Cuplaje in grafuri oarecare 2
1.1 Not ,iunipreliminare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Cuplajemaximale,maxime,perfectesiaproapeperfecte . . . . . . . . 3
1.1.2 Acoperireacumuchii,respectivcunoduri,aunuigraf . . . . . . . . . 4
1.1.3 Multimeindependentădenoduri . . . . . . . . . . . . . . . . . . . . . 4
1.1.4 IdentitatealuiGallai . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 TeoremaluiBerge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 TeoremaluiKoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 TeoremaluiHall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Cuplaje perfecte 10
2.1 Grafsaturatnefactorizabil . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.1 Notiunuipreliminare . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.2 Teoremadestructurăagrafurilorsaturatenefactorizabile . . . . . . . . 10
2.2 TeoremaluiTutte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Condit ,iisuficientepentruexistent ,aunuicuplajperfect . . . . . . . . . . . . . 16
2.3.1 TeoremaluiPetersen . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 TeoremaluiSumner . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.3 TeoremaluiPlesnik . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1

1 Cuplaje in grafuri oarecare
Să considerăm o echipa de fotbal ce are un lot de 11 jucători s ,i tot atâtea pozit ,ii in
teren ce trebuie ocupate. Fiecare pozit ,ie din teren are un anumit specific iar fiecare jucător
poate să fie specializat pe una sau mai multe pozit ,ii (mijlocas ,dreapta, fundas ,central, portar).
Prinurmare,oproblemapoateconstaîngăsireauneiconfigurat ,iiîncarefiecarejucătorsajoace
pe o pozit ,ie conformă specializării sale. Pornind de la această problemă introducem notiunea
decuplajprecums ,ioseriederezultatecesepotrivescînacestcadru.
1.1 Not ,iuni preliminare
Definitie. Într-un graf G= (V; E)numim cuplaj o mult ,ime de muchii Nunde oricare doua
muchiinusuntincidentecuacelas ,inod. Nodurilegrafului Gceseaflălaextremitat ,ilemuchiilor
dinNle vom numi Nsaturate iar pe celelalte le vom numi Nnesaturate .
Definitie. Fie un graf G= (V; E)s,iNun cuplaj al acestuia. Numim lant ,alternant relativ la
cuplajul Nunlant ,elementarformatinmodalternativdinmuchiialemultimilor Ns,iE(N)N.
Definitie. Într-un graf G= (V; E)un lant ,alternant relativ la un cuplaj Nse numes ,te deschis
dacă are extremităt ,ile N-nesaturate s ,i închis în cazul în care extremităt ,ile sunt N-saturate.
Figura1.1.0.1: Cuplajeîntr-ungrafneorientat
Exemplu. Înfigura1.1.0.1,mult ,imeaN=f(5;6);(1;4);(0;2);(3;7)gesteuncuplajiarmult ,imea
L=f(8;6);(6;5);(5;0);(0;2);(2;3);(3;7)greprezintăunlant ,alternantrelativlacuplajul M.
2

1.1.1 Cuplaje maximale, maxime, perfecte si aproape perfecte
Definitie. Uncuplaj Ndintr-ungraf G= (V; E)senumes ,temaximaldacăpentruoricemuchie
u2V(G)mult,imeaN[ fugnu reprezintă un cuplaj al grafului G.
Definitie. Uncuplaj Malunuigraf G= (V; E)senumestemaximdacaindeplinestecondit ,ia:
jHj  jMjpentru orice cuplaj HdinG. Cardinalitatea unei astfel de mult ,imi o vom nota cu
v(G).
Observatie. Oricecuplajmaximestemaximalînsănuoricecuplajmaximalestemaxim. Acestă
remarcăpoatefiusordeobservatprintr-unexemplu.
Exemplu. În figura 1.1.1.1, cuplajul H=f(2;4);(6;7)geste cuplaj maximal însă nu este
maximiarcuplajul M=f(1;2);(4;5);(6;7)gestemaximals ,imaxim.
Figura 1.1.1.1: Cuplaj maximal s ,i
maxim
Figura1.1.1.2: Cuplajperfect
Definitie. Un cuplaj Mal unui graf G= (V; E)se numes ,te perfect dacă orice nod al grafului
esteMsaturats,i aproape perfect dacă există un singur nod Mnesaturat înG.
Observatie. Oricegrafcecont ,ineunnumărimpardenodurinupoatecont ,ineuncuplajperfect.
Observatie. Oricecuplajperfectestes ,icuplajmaxim.
Exemplu. Înfigura1.1.1.1,mult ,imeaM=f(1;2);(4;5);(6;7)gesteuncuplajaproapeperfect
iarînfigura1.1.1.2, R=f(1;3);(4;6);(2;7);(5;8);(9;10)greprezintăuncuplajperfect.
3

1.1.2 Acoperirea cu muchii, respectiv cu noduri, a unui graf
Definitie. Fieungraf G= (V; E)s,iNE(G). Mult,imeaNsenumes ,teacoperirecumuchii
a grafului Gdacă pentru orice v2V(G)există cel put ,in o muchie e2Nastfel încât eeste
incidentă cu nodul v. Vom nota cu (G)cardinalitatea celei mai mici acoperiri cu muchii.
Observatie. Oricecuplajperfectesteoacoperirecumuchii.
Definitie. Fie un graf G= (V; E)s,iSV(G). Mult,imea Sse numes ,te acoperire cu noduri
a grafului Gdacă pentru orice e2E(G)există cel put ,in un nod v2Sastfel încât muchia e
incidentă cu v. Vom nota cu (G)cardinalitatea celei mai mici acoperiri cu noduri.
Figura1.1.2.1: Acoperirecunoduri,respectivmuchii,agrafului
Exemplu. înfigura1.1.2.1,mult ,imeaM=f(1;7);(1;6);(0;5);(2;4);(2;3)gesteoacoperire
cu muchii a grafului. De remarcat este că această mult ,ime nu este un cuplaj. Mult ,imea N=
f0;1;2;5gesteoacoperirecunoduri.
1.1.3 Multime independentă de noduri
Definitie. O mult ,ime de noduri Hdin graful G= (V; E)se numeste mult ,ime independentă
dacăintreoricaredouănoduri v1; v22Hmuchia v1v2/2E(G). Cardinalitateaceleimaimari
mult,imi independente de noduri din Go notăm cu (G).
Figura1.1.3.1: Mult ,imeindependentădenoduri
4

Exemplu. Îngrafuldinfigura1.1.3.1, N=f1;3;5;8gesteomult ,imeindependentădenoduri
.
1.1.4 Identitatea lui Gallai
Continuăm această lucrare cu prezentarea unui rezultat ce îmbină o mare parte din
informat ,iileprezentateînintroducereaacestuicapitol.
Teorema. Fie un graf G= (V; E). Atunci :
(a)(G) +(G) =jV(G)j
(b)Dacă Gnu are noduri izolate atunci v(G) +(G) =jV(G)j
Demonstrat ,ie.Prima afirmatie reiese imediat din faptul că dacă notăm cu Mcea mai mare
mult,imeindependentadenoduriatuncimult ,imeacomplementarăreprezintăceamaimicăacoperire
cunoduriagrafului.
Pentruademonstraadouaafirmatievomnotacu Hceamaimicăacoperirecumuchii
a lui G. Eliminând muchiile din Gce nu apartin lui Hobtinem un graf partial ce cont ,ine
jV(G)j (G)componentedijuncte. Datorităfaptuluicănuexistănoduriizolatein Gfiecare
dinacestecomponentecont ,inecelput ,inomuchie. Selectândcâteomuchiedinfiecarecompo-
nentăobt ,inemuncuplajpecareîlvomnotacu M. Prinurmare v(G) jMj=jV(G)j (G)
deundededucemcă
v(G) +(G) jV(G)j (1)
Pentru inegalitatea inversă alegem un cuplaj maxim M. Vom nota cu Umult,imea
nodurilorcenusuntacoperitede M. Datorităfaptuluică Gnuarenoduriizolatepentrufiecare
dintrecele jV(G)j2v(G)nodurialelui Uputemalegeomuchiecaresaleacopere. Vomnota
cuScolect,iademuchiialesemaisus. Înmodevident M[Sreprezintăoacoperirepentru G.
Prinurmare (G) jM[Sj=v(G) +jV(G)j 2v(G)deundededucemcă
v(G) +(G) jV(G)j (2)
Concluzionând,din(1)s ,i(2)reiesecă v(G) +(G) =jV(G)j. 
1.2 Teorema lui Berge
Pentru început vom face doua observat ,ii ce ne vor fi utile în demonstrarea teoremei
luiBerge.
5

Observatie. Fie graful G= (V; E)s,iN1,N2doua cuplaje ale acestuia ( N1cuplaj cu linie
ingrosată, N2cuplajculiniezimt ,ată). Considerăm Hgrafulindusdediferent ,asimetricăacelor
douacuplaje. Componenteleconexealegrafului Hpotfidepatrutipuri:
(a)Ciclu N1,N2alternant (Numităs ,icomponentadetip C)(Figura1.2.0.1).
Figura1.2.0.1
(b)LantN1,N2alternant cuoextremitate N1saturats,icealaltă N2saturat
(componentetip (N1; N2))(Figura1.2.0.2)
Figura1.2.0.2
(c)LantN1,N2alternant cuambeleextremităt ,iN1saturate(componentetip
(N1; N1))(Figura1.2.0.3)
Figura1.2.0.3
(d)LantN1,N2alternant cuambeleextremităt ,iN2saturate(componentetip
(N2; N2))(Figura1.2.0.4)
Figura1.2.0.4
Observatie. Pentruoricedouacuplaje N1s,iN2aleunuigraf G= (V; E)avem: jN1jjN2j=
numărul componentelor conexe din subgraful indus de N1
N2de tipul (N1; N1)- numărul
componentelor conexe din subgraful indus de N1
N2de tipul (N2; N2)unde
este diferent ,a
simetrică a doua mult ,imi.
6

Teorema. FieG= (V; E)ungrafsi Nuncuplajalacestuia. Atunci Nesteuncuplajmaximal
dacă s,i numai dacă nu există în Gnici un lant ,N-alternant deschis.
Demonstrat ,ie.
„)”
FieNuncuplajmaximalalgrafuluiG.Vompresupunecăexistăunlant ,M-alternant
deschis. Notămacestlant ,cuT. Vomdefiniunnoucuplajcafiind N
E(T)unde
reprezintă
diferent ,asimetricăadouamult ,imi. AcestcuplajîlvomnotacuN’(Figura1.2.0.5). Cum Teste
unlant,N-alternantdeschisavemcă jN0j=jNj+ 1. AcestlucrucontrazicefaptulcăNesteun
cuplajmaxim.
Figura1.2.0.5: N0cuplajculinieingrosată, Ncuplajculiniezimt ,ată
„(”
FieNun cuplaj pentru care nu există nici un lant ,N-alternant deschis. Presupunem
căNnu este un cuplaj maximal. Fie N0un astfel de cuplaj maximal. Prin urmare jN0j>
jNj, adică jN0j jNj>0. Conform celei de a doua observat ,ii din acest subcapitol jN0j
jNj=numărulcomponentelorconexedinsubgrafulindusde N0
Ndetip (N0; N0)-numărul
componentelorconexedingrafulindusde N0
Ndetip (N; N )unde
reprezintă,camaisus,
diferent ,asimetricădintredouamult ,imi.
As,adar, deducem că numarul componentelor conexe din subgraful N0
Nde tipul
(N0; N0)estestrictpozitiv,adicăfaptulcăexistăunlantN-alternantdeschis. Acestlucrureprez-
intăocontradict ,ie. 
1.3 Teorema lui Koning
Teorema. Dacă G= (V; E)este un graf bipartit, atunci (G) =V(G).
Demonstrat ,ie.Deoareceoriceacoperiredenoduritrebuiesăacoperefiecarecuplaj,avem
(G)v(G) (1)
7

Pentruaobt ,ineinegalitateainversăvomstergecâtmaimultemuchiidin Gastfelîncât
cardinalitateaceleimaimiciacoperiridenodurisărămânăaceas ,i. Notămcu G0acestsubgraf.
As,adar(G0) =(G), dar (G0e)< (G)pentru orice e2V(G0). Vom demonstra că
E(G0)reprezintă un cuplaj. Presupunem că nu este un cuplaj. Prin urmare trebuie să existe
douamuchii as,ibcareîmpartacelas ,inod x. Neîndreptămatent ,iaasupragrafului G0a. Prin
minimitateagrafului G0existăoacoperiredenoduri SaînG0acujSaj=(G0)1. Înmod
clarnicioextremitatealui anuseaflăîn Sa. Înmodsimilarexistăoacoperire SbînG0bcu
jSbj=jSaj=(G0)1carenucont ,inenicioextremitatealui b.
Acumformămsubgraful G00indusde G0,G00=G0[(Sa
Sb)[fxg]unde
reprezintă
diferent ,asimetricadouamult ,imi. Fie t=jSa\Sbj. Atunci jV(G00)j= 2((G0)1t) + 1s,i
deoarece G00esteungrafbipartit,existăomult ,imeTcareacoperă G00cujTj (G0)1t.
Daracum T0=T[(Sa\Sb)reprezintăoacoperiredenodurialui G0. Pentruavedea
acest lucru să presupunem că geste o muchie aleasă în mod aleator din G0. Dacă g6=asau
b,atunci gfieesteacoperitde Sa\Sb,fieesteomuchieagrafului G00s,iesteacoperităde T(
figura1.3.0.1). Dacă gesteunadinmuchiile asaubatunciesteacoperitde T.
Figura 1.3.0.1: In subgraful G00nodurile duble sunt in Saiar nodurile ingrosate sunt in Sb
Insubgraful G0[Sa\Sb]nodurilenegresuntin Sa\Sb
Astfel (G0) jT0j=jT[(Sa\Sb)j=jTj+jSa\Sbj (G0)1t+t=(G0)1,
contradict ,ie. As,adarG0reprezintăuncuplaj. Prinurmare
(G) =(G0) =v(G0)v(G) (2)
Dinafirmatiile(1)s ,i(2)deducemcă (G) =V(G). 
8

1.4 Teorema lui Hall
9

2 Cuplaje perfecte
2.1 Graf saturat nefactorizabil
Înaceastăsect ,iunevomaduceîndiscut ,ienot,iuneadegrafsaturatnefactorizabil. Rezul-
tateleprezentatesevordovediutileîncadruldemonstrat ,ieiTeoremeiluiTutte.
2.1.1 Notiunuipreliminare
Definitie. Un graf Gse numes ,te factorizabil dacă cont ,ine un cuplaj perfect.
Definitie. Ungraf Gcecont ,ineuncuplajperfectestesaturatdacăgraful G+earemaimulte
cuplaje perfecte decât graful Gpentru orice muchie e/2E(G).
Definitie. Un graf Geste saturat nefactorizabil dacă Gnu are un cuplaj perfect, însa graful
obt,inut prin adăugarea oricărei alte muchii cont ,ine un cuplaj perfect.
Figura2.1.1.1: Grafsaturatnefactorizabil
2.1.2 Teorema de structură a grafurilor saturate nefactorizabile
Următorul rezultat ne va fi util în demonstrarea Teoremei de structură a grafurilor
saturatenefactorizabile.
Lema.Dacă Geste un graf saturat nefactorizabil s ,iSmult,imea nodurilor ce au gradul
jV(G)j 1atunci componentele grafului GSsunt grafuricomplete.
Demonstrat ,ie.Fieabs,ibcdouămuchiiadiacentedingraful GS. Pentruadovediafirmat ,ia
noastră este suficient să demonstrăm că nodurile as,icsunt adiacente. Vom presupune că
10

nodurile as,icnusuntadiacente. As ,adartrebuiesăexisteunnod dînGastfelîncat bd/2E(G)
(Figura2.1.2.1). Încazcontrar bs-araflaîn S.
Figura2.1.2.1
CumGesteungrafsaturatnefactorizabilatuncigraful G[abcont,ineuncuplajperfect
pecareîlvomnotacu F1. Esteevidentcă ac2F1. Similars ,iG[bdcont,ineuncuplajperfect
F2cubd2F2.
Înacestmomentnevomîndreptaatent ,iaasupragrafuluiindusdediferent ,asimetrică
dintrecuplajele F1s,iF2. Laacestgraftoatecomponentelesuntcicluridelungimepară. Vom
considera T1ciclulcecont ,inemuchia acs,iT2ciclulcecont ,inebd.
Putemdistingedouacazuriposibile:
(a)Ciclurile T1s,iT2suntdiferite(Figura2.1.2.2). Înacestcazvomconsideragraful
indusdediferent ,asimtricădintrecuplajul F1s,iE(T1). Astfelvomobservacămuchiileacestui
graf reprezinta un cuplaj perfect pentru G. Acest lucru reprezintă o contradinct ,ie deoarece G
estesaturatnefactorizabil.
Figura2.1.2.2: Cuplajul F1culiniecurbată
Cuplajul F2culinieîngros ,ată
Figura2.1.2.3: Cuplajul F1culiniecurbată
Cuplajul F2culinieîngros ,ată
(b)Ciclurile T1s,iT2coincid (Figura 2.1.2.3). Vom considera că nodurile b,d…c,
ase află exact in această ordine. Cazul b,d…a,cse trateaza echivalent. Dacă notăm cu P
11

multimea muchiilor din portiunea b,d…c, mult,imea P[bcreprezintă un ciclu. Prin urmare
muchiilegrafuluiindusde F2s,iP[bcreprezintăuncuplajperfectalgrafului G. Acestlucru,
cas,iînprimulcaz,reprezintăocontradict ,iedeoarece Gesteungrafsaturatnefactorizabil.
Înconcluzie,componentelegrafului GSsuntgrafuricomplete. 
Teorema. Un graf Geste saturat nefactorizabil dacă s ,i numai dacă are urmatoarea structură
(a)Gare un numărimparde noduri s ,i este complet
sau
(b)Gareunnumarpardenoduris ,iesteformatdinsubgrafuricompletecunoduridijuncte S0,
G1,G2,Gkastfelîncat k=jS0j+ 2,fiecare Giareunnumarimpardenoduris ,ifiecarenodal
fiecarui subgraf este conectat cu fiecare nod al lui S0(Figura 2.1.2.5).
Figura2.1.2.4
Demonstratie .
„=>”
Considerăm Gungrafsaturatnefactorizabil.
Dacă Gare un numar impar de noduri atunci este evident că nu are un cuplaj per-
fect. Prinurmaredoargrafulcompletîndeplines ,tecerint ,adegrafsaturatnefactorizabildeoarece
acestaestesingurulcăruianuisemaipotadăugamuchii.
Dacă Gare un numar par de noduri atunci vom defini S0ca în lema anterioară. Fie
G1,G2,…Gkcomponenteconexealegrafului GS0. Conformlemeianterioare G1,G2,…Gk
suntgrafuricompleteiarprindefinit ,ialui Sfiecarenodaluneicomponente Giesteadiacentcu
12

fiecarenodallui S. Dacăcelmult jS0jcomponentedin GS0suntimpareatuncigraful Gva
cont,ineuncuplajperfect. Acestlucrureprezintăocontradict ,iecufaptulcă Gestegrafsaturat
nefactorizabil. Prinurmare GS0arecelput ,injS0j+1componenteimpare,iardatorităparitat ,ii,
arecelput ,injS0j+ 2componenteimpare. Dacă GS0aremaimultde jS0j+ 2componente
impare, prin conectarea a doua noduri dintre acestea vom obt ,ine un graf ce nu are un cuplaj
perfect. Acest lucru contrazice faptul că G este saturat nefactorizabil. Astfel graful GS0
areexact jS0j+ 2componenteimpare. Referitorlaexistent ,auneicomponentepareaceastanu
e posibilă deoarece prin adăugarea unei muchii între componenta pară s ,i oricare componentă
grafulrezultatnuvacont ,ineuncuplajperfect.
„<=”
Dacăgraful Grespectăcriteriul (a)atunciesteclarcăestesaturatnefactorizabil.
Încontinuarevomarătacădacăgraful Grespectacriteriul (b)atunciestesaturatne-
factorizabil. Datorităfaptuluică jS0jdepăs,es,tecardinalitateacomponentelorimpare, graful G
nupoateaveauncuplajperfect. Rămânesăarătamcăpentruoricemuchieceoadăugamin G,
grafulrezultatvacontineuncuplajperfect. Consideram eomuchiecuproprietateaca e/2E(G).
Întrucâtmult ,imeanodurilordin S0esteformatădinnoduriceaugradul jS0j1iarG1; G2:::G k
sunt subgrafuri complete, muchia epoate lega doar două subgrafuri complete. Considerăm că
celedouăsubgrafurisuntnotatecu Gks,iGk1. Notămcu H=Gk[Gk1[e. Acestsubgraf
cont,ineuncuplaj M1cesatureazatoatenodurile(Figura2.1.2.5). Eviden e2M1.
Figura2.1.2.5
Notăm cu v1; v2; :::v k2nodurile din S0. ÎnGHrămân subgrafurile complete cu
noduri dijuncte S0; G1; :::G k2ce au carcateristicile din criteriul (b). Prin urmare pentru orice
i= 1;2::; k2,Gicont,ine un cuplaj, notat cu Ti, ce saturează jGij 1noduri. Vom nota cu
M2=T1[T2[:::[Tk2s,i cuu1; u2; :::u k2nodurilor nesaturate din G1; G2; :::G k2. Din
definit,ialui S0deducemcăexistamuchiile v1u1; v2u2; :::v k2uk2. As,adarmultimeademuchii
13

M1[M2[v1u1[v2u2[:::[vk2uk2satureazătoatenodurilelui G(Figura2.1.2.6). Cum e
afostalesînmodarbitrardeducemcăGesteungrafsaturatnefactorizabil.
Figura2.1.2.6

2.2 Teorema lui Tutte
Săpresunpunemcăavemungraf Gcarecont ,ineomult ,imedenoduri Scuproprietatea
cănumărulcomponentelorimparedepăs ,es,tejSj. Înacestcazesteclarcă Gnupoatecont ,ineun
cuplajperfect. RemarcabillaTeoremaluiTutteestecăvalideazăexistent ,aunuicuplajperfectîn
cazulîncarenuexistăomult ,imeSînGcuproprietateademaisus. Notămcu co(G)mult,imea
componentelorimparedintr-ungrafG.
Teorema. Un graf Gare un cuplaj perfect dacă s ,i numai dacă co(GS)jSjpentru orice
SV(G).
Demonstrat ,ie.
„)”
FieGun graf ce cont ,ine un cuplaj perfect. Fie So multime arbitrară de noduri din
V(G)s,iG1; G2; :::G kcomponenteleimparedin GS. Pentrufiecare i= 1;2::k,noduriledin
Gipotfiadiacentecualtenoduridin Gis,icunoduriledin S. Cum Gareuncuplajperfect,cel
put,in un nod din fiecare Gitrebuie să fie cuplat cu un nod diferit din S. Prin urmare numărul
nodurilordin Sestecelput ,ink,număruldecomponenteimpare. Înconcluzie co(GS)jSj
pentruorice SV(G).(Figura2.2.0.1).
14

Figura2.2.0.1
„(”
Vom presupune că Gsatisface criteriul co(GS)jSjpentru orice SV(G)
însă nu are un cuplaj perfect. Adăugăm muchii in graful Gpână când obt ,inem un graf saturat
nefactorizabil. Fie G0grafulsaturatnefactorizabilobt ,inutprinprocedurademaisus.
DacăGareunnumărimpardenodurialegând S=;vedemcaGnusatisfacecriteriul
dinipoteza.
Dacă G are un numar par de noduri consideram S0mutimea de noduri din G0ce au
gradul jV(G)j 1. Teoremadestructuraagrafurilorsaturatenefactorizabiledescriestructura
grafului G0S0. Structura acestuigrafnueste vidăîntrucât Gnuafostcomplet(Daca Gera
completaveauncuplajperfect). Prinurmare
G0S0=G1[G2[:::[Gk
unde G1; G2:::G ksunt subgrafuri complete cu noduri dijuncte cu k= jS0j+ 2. As ,adar G are
mai mult de jS0jcomponente impare. Dacă eliminăm acum toate muchiile E(G0)E(G)ce
le-aminseratîngraful G,fiecarecomponentăimparădingraful G0S0dănas,terelacelput ,in
o componentă impară in GS0. Acest S0contrazice ipoteza. În acest moment se incheie
demonstrat ,iateoremei. 
15

2.3 Condit ,ii suficiente pentru existent ,a unuicuplajperfect
Existăoseriedeconditiisuficientepentruexistentaunuicuplajperfectceimplicasi
alteproprietatialeagrafurilor. Inaceastsubcapitolvomfacereferireladouadintreacestea.
2.3.1 Teorema lui Petersen
Teorema. Orice graf 3-regulat ce nu cont ,ine muchii critice cont ,ine un cuplaj perfect.
Demonstratie .Considerăm Gun graf 3-regulat fară muchii critice s ,i o mult ,imeScu propri-
etateacă SV(G). FieG1; G2; :::G kcomponenteleimparedin GSs,iminumarulmuchiilor
ceauunnodin V(Gi)s,icelalaltîn Spentruorice i= 1;2:::k. Cum Geste3-regulatavem
X
v2V(Gi)deg(v) = 3jGijs,iX
v2Sdeg(v) = 3jSj
.
Acum, pentru orice i= 1;2:::k,E(Gi) = [ V(Gi); V(Gi)[S][V(Gi); S]unde
[A; B ]reprezintămult ,imeamuchiilorceauunvârfin As,ialtulîn B,AVs,iBV. Prin
urmare
mi=j[V(Gi); S]j=X
v2V(Gi)deg(v)2jE(Gi)j
pentru orice i= 1;2:::k. Deoarece deg(v) = 3pentru orice v2V(G)siG1; G2; :::; G ksunt
componente impare, mieste impar pentru orice i= 1;2:::k. Cum G nu are muchii critice
mi3. Prinurmare
co(GS) =k1
3kX
i=1mi1
3X
v2V(Gi)deg(v) =jSj:
CumSafostaleasăînmodarbitrar,conformTeoremeiluiTuttegrafulGcont ,ineun
cuplajperfect.

Exemplu. Înfigura2.3.1.1estereprezentatgrafulceîipoartănumeleluiJuliusPetersen. Acesta
esteungraf3-regulatfărămuchiicriticecu10nodurisi15muchiicareservestecaexemplusau
contra exemplu pentru multe probleme din teoria grafului. Muchiile cuplajului perfect sunt
îngros,ate. Dement ,ionatestecăaceastăconfigurat ,ieacuplajulperfectnuesteunică.
16

Figura2.3.1.1
Figura2.3.1.2
Observatie. Dacăarfisărenuntamlaipotezaconformcăreiagrafulnucont ,inemuchiicritice
atunciTeoremaluiPetersennuarmaifiadevarată,dupacumaratăs ,ifigura2.3.1.2.
2.3.2 Teorema lui Sumner
Observatie. Grafulbipartit K1;3estecunoscutsisubnumeledegrafgheara(figura2.3.2.1). Un
grafcenucontinesubgrafurighearailvomnumiliberdegheare.
Teorema. Daca G este un graf conex cu un numar par de noduri si liber de gheare atunci G
contine un cuplaj perfect.
Demonstrat ,ie.Presupunem ca Gnu contine un cuplaj perfect. Atunci conform teoremui lui
Tutteexistaomultime SV(G)astfelincat co(GS)>jSj. PrintretoatemultimileluiTutte
exista o cea mai mica multime. Deoarece Geste conex, S6=;, alegem un x2S. Atunci x
trebuie sa fie adiacent cu un nod al unei componente impare din GScaci altfel Sxar fi
omultimeTutte. Presupunemca xesteadiacentcuunnoddinexactocomponentaimpara Ca
luiGS. Atunci SxesteomultimeTuttemaimicadecat Sceacereprezintaocontradictie.
Presupunemca xestelegatdeexactdouacomponenteimparedin GS, numimacestedoua
componente C1,C2. Atuncisubgrafulindusde V(C1)[V(C2)[Xesteimparsiprinurmare
Sxreprezinta o multime Tutte. Si in acest caz acest lucru reprezinta o contradictie. Daca
xeste adiacent cu 3 noduri, fiecare nod facand parte din cate o componenta impara, atunci se
contraziceipotezaconformcareiagrafulesteliberdegheare. 
17

Observatie. Se poate testa dacă un grafic este fără gheare verificând, pentru fiecare nod al
graficului,căgrafulcomplementalvecinilorsăinucont ,ineuntriunghi.
Figura2.3.2.1: Graful K1;3
Figura 2.3.2.2: Complementarul gra-
fulK1;3
2.3.3 Teorema lui Plesnik
Teorema. FieG= (V; E)un graf kregulat, cu un numar par de muchii, ce este (k1)-
muchii-conex. Atunci graful rezultat din stergerea a k1muchii din G are un cuplaj perfect.
Demonstrat ,ie.Notamcu G0grafulrezultatdin Gdupastergereaa k1muchii. Presupunem
caG0nu are un cuplaj perfect. Atunci din Teorema lui Tutte exista o multime de noduri Scu
proprietateaca c0(G0S)>jSjiardatoritafaptuluica jV(G0)jesteparavem c0(G0S)>jSj+
2. FieG1; G2:::G rnumarulcomponentelorimparesi Gr+1; Gr+2:::; G tnumarulcomponentelor
paredin G0S.
In continuare vom nota cu inumarul de muchii din E(G)E(G0)ce leaga Gide
S,inumarulacelormuchiidin E(G)E(G0)celeaga Gideoricarealtacomponenta Gssii
numarulmuchiilordin G0celeaga GideS. Asadar i+i+iestenumarultotaldemuchiice
leaga GideGGisiconformipotezeisuntcelputin k1.
Vom arata ca daca Gieste o componenta impara atunci i+i+ik. Sa pre-
supunem contrariul, adica i+i+i=k1. Atunci suma gradelor subgrafului Gieste
kjV(Gi)j(k1) =k(jV(Gi)j1)+1. Acestlucrunegaranteazacasumaesteimparaceace
reprezintaocontradictiecufaptulca Giesteocomponentaimpara. Prinurmareafirmatiaeste
doveditasiavemurmatoareainegalitate:
tX
i=1i+tX
i=1i+tX
i=1ikt (1)
18

Numarandtoatemuchiileeliminatedin Gpentruaobtine G0avemPt
i=1i+1
2Pt
i=1i
siprinurmare:
2tX
i=1i+tX
i=1i2(k1) (2)
PedealtaparteexistacutotulPt
i=1i+Pt
i=1imuchiiceintrain Ssiprinurmare
2tX
i=1i+tX
i=1i jSj: (3)
Adunandinegalitatile(2)si(3)obtinem:
3tX
i=1i+tX
i=1i+tX
i=1ik(jSj+ 2)2 (4)
Acumcomparandinegalita(1)si(4)avem:
kttX
i=1i+tX
i=1i+tX
i=1i
<3tX
i=1i+tX
i=1i+tX
i=1i
k(jSj+ 2)2< k(jSj+ 2);
Decit <jSj+2. Acestlucrureprezentaocontradictieiardemonstratiaseincheie. 
Corolar. Daca G= (V; E)este un graf k-regulat, (k-1)-muchii-conex, cu un numar par de
noduri atunci fiecare muchie din Gface parte dintr-un cuplaj perfect.
Demonstrat ,ie.Fieeomuchieagrafuluilui Gcearecaextremitatinodurile usiv. CumGeste
k-regulatnotamcu e1; e2:::ek1muchiileincidenecunodulu. TeoremaluiPlesniknegaranteaza
uncuplajperfectingraful Ge1e2::ek1. Cum eestesinguramuchieincidentacuu
dinacestgrafdeducemcafacepartedincuplajulperfect. 
19