Seguendo [23] mostreremo ora come sia possibile generare in modo ricorsivo tutti i grafi gaussiani insieme ai loro cicli gaussiani.
Definiamo l’operazione di eliminazione di un vertice per un grafo gaussiano G con |VG| > 1. Sia v un vertice di G, sia C un ciclo gaussiano di G il cui primo vertice della
successione sia diverso da v e siano e1, e2, e3, e4 gli archi di G incidenti su v numerati
nell’ordine di comparizione in C. Si ha e1 parallelo ad e2 e e3 parallelo ad e4. Possiamo
scrivere
C = nC1, e1, v, e2, C2, e3, v, e4, C3
o .
Dove C1, C2, C3 sono sottocammini eventualmente contenenti un solo vertice di C. `E
possibile che e2 = e3 sia un loop, nel qual caso C2 `e vuoto e C1 6= C3. Consideriamo un
nuovo grafo G|v ottenuto da G eliminando il vertice v nel seguente modo. Rimpiazziamo
gli archi e1 e e3con un unico arco e13definito in modo da avere come estremi gli estremi di
e1 e e3 diversi da v. Rimpiazziamo anche gli archi e2 e e4 con un unico arco e24definito in
modo da avere come estremi gli estremi di e2 e e4 diversi da v. Il grafo G|v cos`ı ottenuto
`
e gaussiano. Sia C−2 il cammino C2 preso in senso inverso. Allora su G|v abbiamo il ciclo
gaussiano C|v = n C1, e13, C−2, e24, C3 o . Nel caso e2 = e3 fosse un loop abbiamo
C|v =
n
C1, e14, C3
o .
Possiamo dunque rimuovere qualsiasi vertice di un qualsiasi grafo gaussiano G con |VG| > 1 per ottenere un grafo gaussiano con un vertice in meno.
Teorema 3.1. Ogni grafo gaussiano G pu`o essere trasformato nel grafo contenente un unico vertice e due loop ripetendo |VG|−1 volte l’operazione di eliminazione di un vertice.
Definiamo ora l’operazione inversa alla precedente, l’operazione di introduzione di un vertice per un grafo gaussiano G.
Sia H un’immersione di G sulla sfera (un grafo isomorfo a G “disegnato” sulla sfera) e C un ciclo gaussiano di G corrispondente ad un ciclo gaussiano di H. La successione degli archi ei
G in C induce un’orientazione sugli archi corrispondenti eiH di H. Sia F una
faccia di H. Diciamo che due archi e1
Ge e2G di G, corrispondenti a due archi e1H e e2H sulla
frontiera di F , sono co-orientati se e1H e e2H posseggono la stessa orientazione rispetto all’orientazione di F . Notiamo che i nuovi archi introdotti dall’operazione di eliminazione di un vertice sono sempre co-orientati tra loro.
Siano e1G e e2Guna coppia di archi co-orientati tali che ϕG(e1G) =
n vG1, vG2 o e ϕG(e2G) = n v3 G, vG4 o
(vertici e archi sono numerati in ordine di apparizione nella successione del ciclo gaussiano C). Si pu`o avere e1
G = e2G (`e un loop) nel qual caso vG1 = vG2 = vG3 = v4G e
possiamo scrivere
C =nC1, e1G, C3
o . Altrimenti possiamo scrivere
C =nC1, e1G, C2, e2G, C3 o . Dove C1 = n v0 G, e0G, ..., v1G o , C2 = n v2 G, ..., vG3 o , C3 = n v4 G, ..., v0G o sono sottocammini, eventualmente costituiti di un solo vertice di C.
Consideriamo un nuovo grafo G|e1G,e 2
G ottenuto da G aggiungendo un nuovo vertice v,
V
G|e1G,e2G = VG ∪ {v} con v /∈ VG, e sostituendo e
1
G e e2G con quattro nuovi archi ei con
i ∈ {1, 2, 3, 4}, E
G|e1G,e2G = EG∪ {e
i} con ei ∈ E/
G, i cui estremi sono definiti nel seguente
modo: ϕ G|e1G,e2G(e i) = nv, vi G o . Nel caso e1
G= e2G sia un loop sostituiamo e1G con tre nuovi archi (uno dei quali `e un loop)
ei con i ∈ {1, 2, 3}, E
G|e1G = EG∪ {e
i} con ei ∈ E/
G, i cui estremi sono definiti nel seguente
modo: ϕ G|e1G(e 1) = ϕ G|e1G(e 2) =nv, v1 G o , ϕ G|e1G(e 3) =nv, vo.
Il grafo cos`ı ottenuto `e gaussiano. Infatti anche il vertice aggiunto v ha grado quattro e troviamo un ciclo gaussiano C|e1G,e2G come segue. Sia C−
2 il cammino C2 preso in senso
C|e1G,e2G = n C1, e1, v, e3, C−2, e 2, v, e4, C 3 o . Nel caso e1
G = e2G possiamo invece scrivere
C|e1G =
n
C1, e1, v, e3, v, e2, C3
o .
Abbiamo il seguente risultato.
Teorema 3.2. Ogni grafo gaussiano G pu`o essere ottenuto dal grafo contenente un unico vertice e due loop ripetendo |VG| − 1 volte l’operazione di introduzione di un vertice.
Sia G un grafo gaussiano e sia C = {v0, e0, ..., ei−1, v0, ei, ..., v0} un suo ciclo gaus-
siano. Nella successione presente in C il vertice di partenza v0 comparir`a tre volte.
Infatti `e presente all’inizio e alla fine come estremo dell’arco iniziale e dell’arco fina- le (che sono consecutivi). `E presente anche come estremo di altri due archi consecu- tivi della successione che sono visitati dal ciclo gaussiano. Tutti gli altri vertici del grafo compariranno invece due volte nella successione presente in C. Il vertice di par- tenza non ha un significato particolare. Se G ha almeno due vertici otteniamo un’al- tro ciclo gaussiano da C prendendo un’altro vertice del grafo come vertice di partenza nel seguente modo. Sia C = {v0, e0, C1, ej−1, vj, ej, C2, ei−1, vj, ei, C3, ek, v0}. Si ha che
Cvj = {vj, ej, C2, ei−1, vj, ei, C3, ek, v0, e0, C1, ej−1, vj} `e un’altro ciclo gaussiano. Abbiamo
quindi numerosi sottocammini chiusi di C, tutti quelli del tipo D = {vj, ej, C2, ei−1, vj}
dove vj ∈ C/ 2. Vediamo adesso cosa si pu`o dire sulla lunghezza di questi sottocammini
chiusi.
Utilizzando la costruzione ricorsiva dei grafi gaussiani vista sopra si pu`o dimostrare il seguente teorema, dovuto a Gauss.
Teorema 3.3. Sia G un grafo gaussiano e sia C un suo ciclo gaussiano. Allora ogni sottocammino chiuso di C `e di lunghezza dispari.
Dimostrazione. Senza perdita di generalit`a, consideriamo un grafo gaussiano piano. Fa- remo la dimostrazione per induzione sul numero k dei vertici del grafo.
Caso k = 1. Un grafo gaussiano con un solo vertice `e il grafo contenente un unico vertice e due loop. In questo caso C consiste in un cammino chiuso che passa una volta per ognuno dei due loop. Un sottocammino chiuso di C perci`o contiene uno solo dei due loop, quindi ha lunghezza dispari e la tesi `e provata.
Sia dunque k > 1 e la tesi verificata fino a k − 1. Dimostriamo che `e vera anche per k. Abbiamo visto che eliminando un vertice di un grafo gaussiano di k vertici si ottiene un grafo gaussiano di k − 1 vertici. Mostreremo che se per assurdo la tesi non fosse vera per un grafo gaussiano di k vertici allora non lo sarebbe nemmeno per un grafo gaussiano di k − 1 vertici contraddicendo l’ipotesi induttiva. Sia dunque G un grafo gaussiano di k vertici con un ciclo gaussiano C. Sia D un sottocammino chiuso di C di lunghezza pari (quindi k `e un intero pari maggiore di uno). Dobbiamo trovare un opportuno vertice v da eliminare, si hanno le seguenti possibilit`a.
1. Esiste un vertice v /∈ D. In questo caso eliminando v otteniamo un grafo gaussiano di k − 1 vertici con un ciclo gaussiano C|v che contiene propriamente D, ciclo di
lunghezza pari. Assurdo.
2. Esiste un vertice v ∈ D tale che tutti e quattro gli archi incidenti su v sono presenti in D. Quindi l(D) ≥ 4. Eliminando tale v otteniamo un grafo gaussiano di k − 1 vertici con un ciclo gaussiano C|v di cui D|v `e un sottocammino chiuso. Si ha che
l(D|v) = l(D) − 2. Quindi D|v `e un ciclo di lunghezza pari. Assurdo.
3. Non esiste un vertice con le propriet`a descritte nei due punti precedenti. Senza perdita di generalit`a possiamo allora prendere C = {v0, e0, ..., ej−1, v0, ej, ..., v0}
e D = {v0, e0, ..., ej−1, v0}. Abbiamo che per ogni vertice vi, due archi incidenti
su vi compaiono in D e due in C \ D. Perci`o Dc = {v0, ej, ..., v0} ha la stessa
lunghezza di D. Visto che il numero dei vertici k `e maggiore di uno ed in C compaiono 2k archi abbiamo che l(D) = k. In questo caso non `e possibile che k sia uguale a due perch´e altrimenti C non sarebbe trasversale. Infatti si avrebbe C = {v0, e0, v1, e1, v0, e2, v1, e3, v0} e D = {v0, e0, v1, e1, v0}. Quindi tutti e quattro
gli archi inciderebbero su v0 e v1 e non potrebbero intersecarsi. Otterremmo che la
frontiera di ognuna delle quattro facce del grafo sarebbe costituita da una coppia di archi. I due archi sulla frontiera di una faccia del grafo non potrebbero essere consecutivi n´e su v0 n´e su v1. Per ogni arco esisterebbe perci`o un secondo arco
consecutivo al primo sia su v0 che su v1, contraddicendo l’ipotesi di C trasversale.
Otteniamo quindi l(D) = k > 2 e in D abbiamo almeno 4 vertici distinti e 4 archi. Consideriamo il vertice v1. Si avr`a che comparir`a una volta in D e una in
Dc. Possiamo allora scrivere C = {v
0, e0, v1, e1, C1, ej−1, v0, ej, C2, ei−1, v1, ei, C3}.
che l(Dc) = 3 + l(C
2) + l(C3), quindi uno tra l(C2) e l(C3) `e dispari e l’altro `e pari.
Analizziamo queste due possibilit`a.
A. Consideriamo il caso in cui l(C2) `e pari. Eliminiamo v1. Abbiamo C|v1 =
{v0, e0(i−1), C2−, ej, v0, ej−1, C1−, e1i, C3}. Prendiamo in considerazione D1 =
{v0, e0(i−1), C2−, ej, v0}. Poich´e l(C2) = l(C2−) si ha che l(D1) = l(C2) + 2 `e pari.
Assurdo.
B. Consideriamo il caso in cui l(C2) `e dispari. Questo significa che esiste l’arco
ej+1∈ C2. Per le ipotesi fatte finora abbiamo dunque vj+1∈ C2e anche vj+1 ∈
C1. Possiamo allora scrivere C = {v0, e0, v1, e1, C1a, es−1, vj+1, es, C1b, ej−1, v0,
ej, vj+1, ej+1, C2a, ei−1, v1, ei, C3}. Abbiamo che C1 = {C1a, es−1, vj+1, es, C1b}
e che C2 = {vj+1, ej+1, C2a}. Otteniamo l(C1) = l(C1a) + l(C1b) + 2 e quindi
l(C1a) + l(C1b) `e un numero dispari. Allo stesso modo l(C2a) `e un numero pari.
Eliminiamo vj+1. Abbiamo C|vj+1 = {v0, e0, v1, e1,
C1a, e(s−1)j, v0, ej−1, C1b−, es(j+1), C2a, ei−1, v1, ei, C3}. Prendiamo in considera-
zione D2 = {v1, e1, C1a, e(s−1)j, v0, ej−1, C1b−, es(j+1), C2a,
ei−1, v1}. Si ha che l(D2) = 5 + l(C1a) + l(C1b−) + l(C2a) `e un numero pari.
Assurdo.
L’ipotesi di avere un sottocammino chiuso D di C di lunghezza pari in un grafo gaussiano piano con k nodi ci ha portato in ogni caso a trovare un grafo gaussiano di k − 1 nodi con un ciclo gaussiano contenente un sottocammino chiuso di lunghezza pari, contraddicendo l’ipotesi induttiva. Il teorema `e cos`ı dimostrato.