Mnogi se životni problemi mogu modelirati uz pomoć grafova. Graf se sastoji od točaka i njihovih spojnica. Tako točke mogu biti ljudi u određenom društvu, a spojnice parovi prijatelja, ili točke mogu biti električne komponente, a spojnice električna mreža itd.

Grubo govoreći, graf je familija točaka, koje nazivamo vrhovima, zajedno sa spojnicama među njima, koje nazivamo bridovima. Precizna definicija glasi:



Ako su nekom bridu e\in E pridruženi vrhovi u,v\in V, kažemo da su u i v krajevi brida e. Kažemo još i da su vrhovi u i v incidentni s bridom e, da su u i v susjedni vrhovi te pišemo e=uv. Bridovi s barem jednim zajedničkim krajem zovu se susjedni bridovi. Brid čiji se krajevi podudaraju zove se petlja, a brid čiji su krajevi različiti pravi brid ili karika. Dva ili više bridova koji imaju isti par krajeva zovu se višestruki bridovi. Graf koji nema petlji i višestrukih bridova nazivamojednostavnim grafom. Mi ćemo se ovdje baviti samo jednostavnim grafovima i pod pojmom graf podrazumijevati samo takve grafove.




Primijetimo da je u jednostavnom grafu šetnja potpuno određena nizom svojih vrhova v_{0}v_{1}v_{2}...v_{m-1}v_{m}.



Da bismo dobili predodžbu o tome kakvim se problemima bavi teorija sparivanja, počnimo s dva jednostavna primjera koja dobro ilustriraju taj problem.




Ako izvršitelje i poslove, odnosno djevojke i momke, uzmemo za vrhove grafa, a bridovima spojimo svakog izvršitelja s poslovima koje zna obavljati, odnosno sve djevojke i momke koji se međusobno simpatiziraju, onda naš problem glasi: odredite maksimalan broj bridova od kojih nikoja dva nisu susjedna.





Ako je E\neq\emptyset, onda je svaki jednočlani podskup od E jedan primjer sparivanja u G. No, zanimljivo je naći sparivanje sa što većim brojem bridova. Stoga definiramo:




U literaturi se savršeno sparivanje često zove Kekuléova struktura, prema njemačkom kemičaru Augustu Kekuléu (1829. – 1896.).

Očito je svako savršeno sparivanje ujedno i maksimalno, dok obrat općenito ne vrijedi. Nadalje, broj bridova u savršenom sparivanju je konstantan i iznosi \frac{\left\vert V\right\vert }{2}. Za postojanje savršenog sparivanja nužno je da graf ima paran broj vrhova. No, to je samo nuždan, a ne i dovoljan uvjet za postojanje savršenog sparivanja. Osnovni problem teorije sparivanja jest ispitati postoji li savršeno sparivanje i ako postoji, konstruirati ga. U slučaju da se ne može konstruirati savršeno sparivanje, cilj je konstruirati sva ili bar neka maksimalna sparivanja.



Označimo s

\bullet	v(G)= kardinalnost maksimalnog sparivanja u G,
\bullet	\alpha(G)= kardinalnost maksimalnog stabilnog skupa u G,
\bullet	\tau(G)= kardinalnost minimalnog vršnog pokrivača od G,
\bullet	\rho(G)= kardinalnost minimalnog bridnog pokrivača od G.

Primijetimo da je \rho(G) dobro definiran samo za grafove bez izoliranih vrhova.

Neka je K neki vršni pokrivač grafa G, a M neko sparivanje u G. Tada svaki brid iz M ima barem jedan kraj u K, a budući da bridovi iz M nemaju zajedničkih vrhova, to je \left\vert M\right\vert \leq\left\vert K\right\vert. Stoga i za maksimalno sparivanje M^{\ast} i minimalni vršni pokrivač \bar{K} također vrijedi \left\vert M^{\ast}\right\vert \leq\left\vert \bar{K}\right\vert, tj. \upsilon (G)\leq\tau(G).

Slično, ako je L bridni pokrivač grafa G, a S stabilan skup, onda je \left\vert S\right\vert \leq\left\vert L\right\vert jer je svaki vrh iz S kraj barem jednom bridu iz L, a nikoja dva vrha iz S nisu susjedna. Stoga je \alpha(G)\leq\rho(G). Nadalje, vrijedi teorem



Iz ovog odmah slijedi da je \alpha(G)+\tau\left( G\right) =\left\vert V\right\vert . Slično, v(G)+\rho\left( G\right) =\left\vert V\right\vert, tj. kardinalnost maksimalnog sparivanja i minimalnog bridnog pokrivača u sumi daju ukupan broj bridova grafa G, iako komplement sparivanja ne mora biti bridni pokrivač, kao što je slučaj sa stabilnim skupom i vršim pokrivačem.

Jedan od osnovnih pojmova teorije sparivanja je pojam uvećavajućeg puta.




Ovaj teorem omogućuje nam da provjerimo je li neko sparivanje M u grafu G maksimalno, kako bismo ispitali postoji li ili ne M-uvećavajući put.




Vidjeli smo da u svakom grafu vrijedi nejednakost \upsilon(G)\leq\tau(G). No, sljedeći teorem kaže da u bipartitnom grafu vrijedi \upsilon (G)=\tau(G).




Potpuno sparivanje, dakle, definira jedno 1-1 preslikavanje između vrhova iz X i jednog dijela vrhova iz Y koje odgovarajuće vrhove iz X i Y spaja bridom. Stoga za svakih k vrhova iz X mora postojati barem k njima susjednih vrhova u Y. To je, dakle, nuždan uvjet za postojanje potpunog sparivanja. Sljedeći teorem kazuje da je to i dovoljan uvjet.



Ako particije X i Y imaju jednak broj elemenata, onda su potpunim sparivanjem u X zasićeni i svi vrhovi iz Y, pa je riječ o savršenom sparivanju u bipartitnom grafu. O tome govori sljedeći teorem popularno nazvan Teorem o braku.



Primjenjujući ovaj teorem na uvodne primjere 4 i 5, lako ćemo odgovoriti na pitanja koja se u njima postavljaju. Označimo li sa K=\left\lbrace K_{1},K_{2},K_{3},K_{4},K_{5}\right\rbrace skup svih kandidata, a sa P=\left\lbrace P_{1},P_{2},P_{3},P_{4},P_{5}\right\rbrace skup svih poslova, tada problem možemo predstaviti bipartitnim grafom G=\left( K,P\right), a pitanje je li moguće rasporediti kandidate na poslove tako da svi kandidati obavljaju posao za koji su kvalificirani i da se svi poslovi obavljaju, ekvivalentno je pitanju postoji li u tom grafu savršeno sparivanje. Pogledajmo skup S=\left\lbrace K_{1},K_{2},K_{4}\right\rbrace \subset K. Kako je kandidat K_{1} kvalificiran za poslove P_{3},P_{4}, kandidat K_{2} za posao P_{3}, a kandidat K_{4} za poslove P_{3},P_{4}, tako je skup svih vrhova koji su susjedni skupu S jednak N\left( S\right) =\left\lbrace P_{3},P_{4}\right\rbrace. Stoga je \left\vert N\left( S\right) \right\vert \lt \left\vert S\right\vert, pa nije zadovoljen Hallov uvjet, što znači da ne postoji savršeno sparivanje u ovom grafu. Dakle, nije moguće rasporediti kandidate na poslove tako da svi kandidati obavljaju posao za koji su kvalificirani, a da se svi poslovi obavljaju.

No, u bipartitnom grafu koji odgovara problemu iz Primjera 4 vrijedi Hallov uvjet za svaki podskup skupa djevojaka, pa stoga postoji savršeno sparivanje u tom grafu, tj. možemo povezati sve parove poštujući navedene simpatije. Naravno, sada se postavlja pitanje kako konstruirati to sparivanje. Sam Hallov uvjet bez dodatnih razmatranja ne bi bio koristan u praksi jer za bipartitni graf G\left( X,Y\right) treba ispitati sve podskupove skupa X, a broj podskupova naglo raste kako raste broj vrhova. Tako bi, naprimjer, za graf kojemu je \left\vert X\right\vert =50 trebalo ispitati 1125899906842623 različitih podskupova od X.


Pored samog pitanja egzistencije savršenog sparivanja u bipartitnom grafu, jednako je važno i pitanje njegove konstrukcije u slučaju da takvo sparivanje postoji. Jedna od poznatih metoda koja se bavi pitanjima egzistencije i konstrukcije savršenog sparivanja u bipartitnom grafu je tzv. mađarska metoda. S pomoću nje se ili konstruira savršeno sparivanje u bipartitnom grafu G\left( X,Y\right), ili se pronađe podskup S\subseteq X za koji je \left\vert N\left( S\right) \right\vert \lt \left\vert S\right\vert, pa po Hallovu teoremu slijedi da savršeno sparivanje u G\left( X,Y\right) ne postoji.

Ideja je sljedeća:

Započnemo s nekim sparivanjem M u bipartitnom grafu G\left( X,Y\right), pri čemu za M možemo uzeti i prazan skup ako ne znamo ništa bolje. Ako M zasićuje X, onda je ono i savršeno sparivanje, pa smo gotovi. Ako, pak, postoji M-nezasićen vrh u\in X, onda algoritam sustavno traži M-uvećavajući put P s početkom u vrhu u. Ako takav put postoji, onda za sparivanje M^{\prime}=M\bigtriangleup E\left( P\right), gdje je E\left( P\right) skup bridova puta P, sadržava više bridova i zasićuje više vrhova u X nego sparivanje M. Tako dobivamo veće sparivanje M^{\prime}, a potom cijeli postupak ponovimo tako da umjesto polaznog sparivanja M uzmemo sparivanje M^{\prime }. U slučaju da takav put ne postoji, pronađemo skup R svih vrhova koji su s vrhom u povezani M-alternirajućim putom. Može se pokazati da za skup S=R\cap X vrijedi \left\vert N\left( S\right) \right\vert \lt \left\vert S\right\vert, pa po Hallovu teoremu zaključujemo da ne postoji savršeno sparivanje u bipartitnom grafu G\left( X,Y\right), a po Teoremu 12 da je sparivanje M maksimalno sparivanje u G.

Ovaj algoritam dao je J. Edmonds 1965. godine, a zove se mađarska metoda jer se zasniva na idejama dvojice Mađara: Kőniga i Egerváryja.

Algoritam:

Ulaz. Bipartitni graf G s biparticijom (X,Y), \left\vert X\right\vert =\left\vert Y\right\vert.

Izlaz. Savršeno sparivanje M u G ili skup S\subseteq X za koji je \left\vert N\left( S\right) \right\vert \lt \left\vert S\right\vert.


Korak 1. Neka je M bilo koje sparivanje od G, npr. M=\emptyset.

Korak 2. Ako je XM-zasićen, stop (M je tada savršeno sparivanje od G).

U protivnom, neka je vrh x\in XM-nezasićen.

Stavimo S=\left\lbrace x\right\rbrace ,T=\emptyset.

Korak 3. Ako je N\left( S\right) =T, stop (\left\vert N\left( S\right) \right\vert \lt \left\vert S\right\vert).

U protivnom, neka je y\in N\left( S\right) \setminus T.

Korak 4. Ako je y\in YM-zasićen vrh, neka je zy\in M.

Zamijenimo S sa S\cup\left\lbrace z\right\rbrace, a T sa T\cup\left\lbrace y\right\rbrace i vratimo se na korak 3.

Ako je yM-nezasićen vrh, neka je PM-uvećavajući (x,y)-put.

Zamijenimo M s M\bigtriangleup E\left( P\right) i vratimo se na korak 2.


Pogledajmo kako ovaj algoritam radi na primjeru naših djevojaka i momaka.


Ulaz. Bipartitni graf G(X,Y), X=\left\lbrace D_{1},D_{2},D_{3} ,D_{4}\right\rbrace ,Y=\left\lbrace M_{1},M_{2},M_{3},M_{4}\right\rbrace.


Korak 1. Neka je M=\emptyset.

Korak 2. X nije M-zasićen. Vrh x=D_{1}\in X je M-nezasićen.

Stavimo S=\left\lbrace D_{1}\right\rbrace ,T=\emptyset.

Korak 3. N\left( S\right) =\left\lbrace M_{2},M_{3}\right\rbrace \neq T=\emptyset.

Neka je y=M_{2}\in N\left( S\right) \setminus T=\left\lbrace M_{2},M_{3}\right\rbrace.

Korak 4. y je M-nezasićen vrh. Neka je P=D_{1}M_{2}M-uvećavajući put.

\qquad\qquad M=\left\lbrace D_{1}M_{2}\right\rbrace i vratimo se na korak 2.

Korak 2. X je M=\left\lbrace D_{1}M_{2}\right\rbrace-nezasićen. Vrh x=D_{2}\in X je M-nezasićen.

Stavimo S=\left\lbrace D_{2}\right\rbrace ,T=\emptyset.

Korak 3. N\left( S\right) =\left\lbrace M_{2},M_{4}\right\rbrace \neq T=\emptyset.

Neka je y=M_{2}\in N\left( S\right) \setminus T=\left\lbrace M_{2},M_{4}\right\rbrace.

Korak 4. y=M_{2} je M-zasićen vrh jer je D_{1}M_{2}\in M.

S=S\cup\left\lbrace D_{1}\right\rbrace =\left\lbrace D_{1} ,D_{2}\right\rbrace ,T=T\cup\left\lbrace M_{2}\right\rbrace =\left\lbrace M_{2}\right\rbrace

Vratimo se na korak 3.

Korak 3. N\left( S\right) =N\left( \left\lbrace D_{1},D_{2}\right\rbrace \right) =\left\lbrace M_{2},M_{3},M_{4}\right\rbrace \neq T=\left\lbrace M_{2}\right\rbrace

Neka je y=M_{3}\in N\left( S\right) \setminus T=\left\lbrace M_{3},M_{4}\right\rbrace

Korak 4. y=M_{3} je M-nezasićen.

Neka je P=D_{2}M_{2}D_{1}M_{3}M-uvećavajući (D_{2},M_{3})-put.

M=M\vartriangle E\left( P\right) =\left\lbrace D_{1} M_{3},D_{2}M_{2}\right\rbrace i vratimo se na korak 2.

Korak 2. X jeM=\left\lbrace D_{1}M_{3},D_{2}M_{2}\right\rbrace-nezasićen.

Vrh x=D_{3}\in X je M-nezasićen.

Stavimo S=\left\lbrace D_{3}\right\rbrace ,T=\emptyset.

Korak 3. N\left( S\right) =\left\lbrace M_{1},M_{4}\right\rbrace \neq T=\emptyset.

Neka je y=M_{1}\in N\left( S\right) \setminus T=\left\lbrace M_{1},M_{4}\right\rbrace.

Korak 4. y=M_{1} je M-nezasićen vrh.

P=D_{3}M_{1} je M-uvećavajući (D_{3},M_{1} )-put, E\left( P\right) =\left\lbrace D_{3}M_{1}\right\rbrace

M=M\vartriangle E\left( P\right) =\left\lbrace D_{1} M_{3},D_{2}M_{2},D_{3}M_{1}\right\rbrace i vratimo se na korak 2.

Korak 2. X je M=\left\lbrace D_{1}M_{3},D_{2}M_{2},D_{3}M_{1}\right\rbrace-nezasićen.

Vrh x=D_{4}\in X je M-nezasićen.

Stavimo S=\left\lbrace D_{4}\right\rbrace ,T=\emptyset.

Korak 3. N\left( S\right) =\left\lbrace M_{1}\right\rbrace \neq T=\emptyset.

Neka je M_{1}\in N\left( S\right) \setminus T=\left\lbrace M_{1}\right\rbrace.

Korak 4. y=M_{1} je M-zasićen vrh jer je D_{3}M_{1}\in M.

S=S\cup\left\lbrace D_{3}\right\rbrace =\left\lbrace D_{3} ,D_{4}\right\rbrace ,T=T\cup\left\lbrace M_{1}\right\rbrace =\left\lbrace M_{1}\right\rbrace

Vratimo se na korak 3.

Korak 3. N\left( S\right) =N\left( \left\lbrace D_{3},D_{4}\right\rbrace \right) =\left\lbrace M_{1},M_{4}\right\rbrace \neq T=\left\lbrace M_{1}\right\rbrace

Neka je y=M_{4}\in N\left( S\right) \setminus T=\left\lbrace M_{4}\right\rbrace

Korak 4. y=M_{4} je M-nezasićen.

P=D_{4}M_{1}D_{3}M_{4} je M-uvećavajući (D_{4},M_{4})-put, E\left( P\right) =\left\lbrace D_{4}M_{1},D_{3}M_{1} ,D_{3}M_{4}\right\rbrace,

M=M\vartriangle E\left( P\right) =\left\lbrace D_{1} M_{3},D_{2}M_{2},D_{3}M_{4},D_{4}M_{1}\right\rbrace,

vratimo se na korak 2.

Korak 2. X je M=\left\lbrace D_{1}M_{3},D_{2}M_{2},D_{3}M_{4},D_{4} M_{1}\right\rbrace-zasićen, pa smo gotovi.

M je savršeno sparivanje.


Primijetimo da nam Mađarska metoda daje samo egzistenciju jednog savršenog sparivanja, no ne kaže nam ništa o broju svih mogućih savršenih sparivanja. U praksi nam može biti od važnosti poznavati njihov broj. O tome više u sljedećem poglavlju.


U daljnjem ćemo tekstu najviše pozornosti posvetiti molekularnim grafovima, pa ćemo se za savršena sparivanja koristiti izraz Kekuléove strukture. Kekuléove strukture igraju posebno važnu ulogu u proučavanju benzenoida. Benzenoidni graf je povezani graf čije se ravninsko smještanje sastoji od kongruentnih pravilnih šesterokuta, tako da svaka dva šesterokuta ili imaju zajednički vrh, ili su disjunktni. U literaturi ih ponekad nazivaju i poliheksi, heksagonalne životinje, heksagonalna poliomina, heksagonalni sustavi i sl. Za benzenoid kažemo da je katakondenziran ako nijedan vrh nije incidentan s tri šesterokuta. Za benzenoid kažemo da je benzenoidni lanac ako je katakondenziran i nijedan šeterokut nema tri susjedna šesterokuta. Prebrojavanje savršenih sparivanja ima važne kemijske primjene. Naime, Linus Pauling (dobitnik dviju Nobelovih nagrada) uočio je da se s pomoću Paulingova reda veze (omjer broja Kekuléovih struktura koje udvostručavaju neku vezu i svih Kekuléovih struktura) može izračunati aproksimacija duljine veze među atomima ugljika u benzenoidnim molekulama.


Označimo s G neki molekularni graf, a sa k podgraf koji čini Kekuléovu strukturu, tj. koji se sastoji od nesusjednih bridova grafa G, a svaki vrh grafa G je incidentan s točno jednim bridom u k. Naprimjer, za naftalen se mogu pronaći tri Kekuléove strukture.

S K\left( G\right) označimo broj svih različitih Kekuléovih struktura u grafu G. Da bismo odredili taj broj poslužit ćemo se linearnim rekurzijama na grafu i njegovim podgrafovima. Od samih početaka pa sve do danas, metode za prebrojavanje Kekuléovih struktura temelje se upravo na takvim rekurzijama.

Neka je e proizvoljan brid grafa G. S G-e označimo graf koji se dobije iz grafa G kada mu uklonimo brid e, a s G\circleddash e graf koji se dobije iz grafa G uklanjanjem brida e i svih njemu susjednih bridova. Tada vrijedi jednostavna rekurzija koju je i vrlo lako programirati. Važno je napomenuti da ako se primjenom ove rekurzije na neki izabrani niz bridova grafa G taj graf razbije u nepovezane dijelove, rekurziju tada možemo primijeniti zasebno na svaki njegov pojedini dio. Kod molekularnih grafova pozornost se posvećuje i dobivanju rekurzivne formule za prebrojavanje Kekuléovih struktura u ovisnosti o duljini lanca. Tako Gordonova i Davisonova shema za određivanje broja Kekuléovih struktura u katakondenziranom benzenoidnom lancu ima lagan i praktičan grafički prikaz. Pogledajmo to na sljedećem primjeru. Postupak izgleda ovako:

(1)	U šesterokute grafa koji prikazuje katakondenzirani benzenoidni lanac upisuju se brojevi počevši od jednog kraja i to na način: izvan početnog šesterokuta upiše se broj 1, a u prvi šesterokut upiše se broj 2.
(2)	Svaki broj u ostalim šesterokutima dobije se kao suma onog broja koji je upisan u šesterokut koji je njegov direktni prethodnik (njih dva određuju smjer) i onog koji je upisan u šesterokut neposredno prije skretanja lanca u tom smjeru.
(3)	Broj koji je upisan u zadnji šesterokut lanca upravo je broj Kekuléovih struktura K(G).

U našem primjeru je K(G)=25.



Linearna rekurzija K(G)=K(G-e)+K(G\circleddash e) u slučaju grafova polimera (lanac s mnogo ponavljajućih elemenata — ponavljajuće elemente nazivamo monomerima) ima vrlo elegantan oblik bez obzira na to kakvi su polimeri u pitanju. Mi ćemo se ovdje fokusirati na regularne polimere u kojima se ponavlja ista jedinica monomera. Broj Kekuléovih struktura K_{L} za ciklički lanac polimera duljine L se može izraziti u obliku gdje je T transfer matrica karakteristična za jedinicu određenog monomera, a \rho matrica koja opisuje karakter rubnih uvjeta, npr. krajeva lanca polimera.

Iz matrice T vidljivi su svi različiti načini na koje se Kekuléove strukture mogu načiniti iz jednog uzorka na granici jedne jedinice monomera do drugog uzorka na granici sljedeće jedinice monomera.


Taj lanac može se podijeliti na ćelije monomera kao na slici.


S obzirom na vertikalnu os simetrije ovih šesterokuta razlikujemo lijevi i desni monomer. S lijeve i desne strane osi simetrije je neparan broj vrhova šesterokuta (3), pa moramo imati i neparan broj dvostrukih bridova (bridova u sparivanju) koji sijeku os simetrije. Budući da samo dva lijeva brida sijeku os simetrije, točno je jedan od njih dvostruki brid. Sve mogućnosti za postavljanje dvostrukih veza na granici monomera prikazane su na sljedećoj slici.


U slučaju da je gornji lijevi brid koji siječe os simetrije dvostruki brid, postoje dva načina za nastavak na sljedećoj granici, dok se u slučaju donjeg lijevog dvostrukog brida može nastaviti samo na jedan način jer propada mogućnost donja lijeva dvostruka veza\rightarrow gornja desna dvostruka veza. Naime, ta nas mogućnost dovodi do nezasićenog vrha (vidite donju sliku). Vrhove A i B ne smijemo spojiti dvostrukim bridom jer već imamo jednu dvostruku vezu koja siječe os simetrije, a znamo da može biti samo jedna takva. To znači da vrh B ostaje nezasićen, pa ta mogućnost ne daje savršeno sparivanje.


Dakle, transfer matrica je oblika
Za uske lance (široke par šesterokuta) postoji tek nekoliko mogućih uzoraka, tako da je matrica T malog reda, a nakon njene dijagonalizacije lako se izračuna i tražena potencija matrice T za proizvoljnu duljinu lanca L. No, s povećanjem širine trake w, tj. broja veza koje presijecaju os simetrije, eksponencijalno se povećava i red matrice T, ali ova tehnika sigurno je primjenjiva za širine w\leq 12.



Lijevo od osi simetrije imamo neparan broj vrhova šesterokuta (ima ih 5), pa moramo imati i neparan broj dvostrukih bridova (bridova u sparivanju) koji sijeku os simetrije. Dakle, imamo jedan ili tri dvostruka brida koja sijeku os simetrije. Ispitajmo svaku mogućnost zasebno. Najprije pogledajmo sve mogućnosti u kojima je samo gornji lijevi brid dvostruki:


Očito, sve tri mogućnosti zasićuju sve vrhove, tj. vode do savršenog sparivanja.

Mogućnost srednja lijeva dvostruka veza\rightarrow gornja desna dvostruka veza nije dobra (slika 3). Naime, ta mogućnost dovodi nas do nezasićenog vrha. Vrh A ne možemo zasititi jer već imamo jednu dvostruku vezu koja siječe simetralu, a znamo da u ovom slučaju može biti samo jedna (situaciju s tri dvostruka brida zasebno ćemo ispitati). To znači da vrh A ostaje nezasićen, pa ta mogućnost ne daje savršeno sparivanje.

Ostale dvije mogućnosti (slika 4) srednja lijeva dvostruka veza\rightarrow srednja desna dvostruka veza i srednja lijeva dvostruka veza\rightarrow donja desna dvostruka veza su u redu i dovode nas do savršenog sparivanja.

Sljedeće mogućnosti počinju s donjim lijevim dvostrukim bridom. U prva dva slučaja (slika 5):
donja lijeva dvostruka veza\rightarrow gornja desna dvostruka veza i donja lijeva dvostruka veza\rightarrow srednja desna dvostruka veza nije moguće savršeno sparivanje jer dobivamo nezasićene vrhove (vrh A), dok je situacija donja lijeva dvostruka veza\rightarrow donja desna dvostruka veza u redu.

I napokon, ako su sva tri lijeva brida koja sijeku os simetrije dvostruki bridovi (slika 6), onda sve mogućnosti kad je na desnoj strani samo jedan dvostruki brid ili sva tri, dovode do nezasićenih vrhova početnih i krajnjih šesterokuta.

Dakle, transfer matrica je oblika što možemo poistovjetiti s matricom reda 3 oblika Lako se provjeri da je pa dobivamo broj Kekuléovih struktura u lancu duljine L u eksplicitnom obliku
Uočimo da je ova eksplicitna jednadžba analogna linearnoj rekurziji 1. Ako označimo karakteristični polinom transfer matrice reda n s onda je, po Hamilton-Cayleyevu teoremu, T^{n}=\sum\limits_{i=1}^{n} a_{i}T^{n-i}, pa je
što je prvobitna linearna rekurzija 1.

Za naš primjer strukture polifena je K_{L+1}=K_{L}+K_{L-1}. Primijetimo da je rekurzija uvelike neovisna o krajevima lanca, ali oni utječu na početne vrijednosti na kojima se rekurzija temelji.