OliForum Matematico

Prima di partire, lascio qualche problemino...

Dimostrare che un grafo nel quale ogni punto e' congiunto ad almeno altri 3 (direttamente) contiene un ciclo di lunghezza pari.

Buon divertimento!
Maria

Suppongo G sia connesso (altrimenti ne considero le componenti connesse) e ogni suo vertice abbia almeno grado 3.

Step 1: G possiede almeno un ciclo.
Se così non fosse allora sarebbe un albero.
Quindi avrebbe delle foglie con grado 1 che è assurdo (ogni vertice ha grado almeno 3).
Quindi esiste almeno un ciclo.

Step 2: definisco un procedimento.
Considero un ciclo di G.
Lo chiamo $ R_1 $ e lo coloro di rosso.
Scelgo un vertice di $ R_1 $ che chiamo $ S_1 $.

Parto da $ S_i $, scelgo casualmente il percorso da fare senza tornare indietro , coloro di blù il percorso (quindi sia gli archi che i vertici) effettuato dopo $ S_i $.
Ovvero scelgo casualmente un'arco non ancora colorato tra quelli di $ S_i $ successivamente coloro di blu il vertice a cui arrivo e l'arco scelto e reitero il procedimento.
Prima o poi così facendo incontrerò o un vertice colorato di blu o di rosso.
Infatti il numero di vertici non colorati cala ogni volta che scelgo un'arco da percorrere e la strada percorsa non può terminare "nel vuoto" in quanto ogni vertice ha grado almeno 3.
A questo punto chiamo $ R_{i+1} $ l’insieme dei vertici ( $ S_i $ appartiene a $ R_i $) e degli archi blu.
Se ho incontrato un vertice rosso mi fermo.
Se ho incontrato un vertice blu (che chiamo $ T_{i+1} $) coloro di rosso $ R_{i+1} $ scelgo un vertice $ S_{i+1} $ appartenente al ciclo di $ R_{i+1} $ e distinto da $ T_{i+1} $ e reitero il procedimento.

Step 3: posso applicare il procedimento definito un numero finito di volte.
Reiterando il procedimento aumentano i vertici rossi.
I vertici totali sono in numero finito quindi posso reiterare il procedimento solo un numero finito di volte.
Quindi prima o poi mi fermo e la strada blu (che chiamo $ R_n $) incrocerà un vertice rosso ( che chiamo A).
A appartiene ad $ R_k $.

Step 4: esiste un cilco con determinate proprietà.
Per come è stata effettuata la colorazione scegliendo un qualsiasi vertice di $ R_j $ posso arrivare a $ S_j $ (e quindi a $ R_{j+1} $ ) senza passare due volte sullo stesso vertice di $ R_j $ e passando solo su vertici di $ R_j $.

Quindi da A posso arrivare a $ S_k $ (e quindi a $ R_{k+1} $) senza passare due volte sullo stesso vertice di $ R_k $ e passando solo su vertici di $ R_k $, così da $ R_{k+1} $ posso arrivare a $ R_{k+2} $ e così via fino ad arrivare a $ R_n $ .
Da $ R_n $ posso quindi tornare ad A.
Inoltre se A non appartiene al ciclo di $ R_k $ per arrivare da A fino a $ S_k $ (che vi appartiene) devo passare da $ T_{k} $.

Esiste quindi un ciclo che passa per tutti gli $ R_{i=k}^{n} $ in particolare che passa per A e $ S_k $.
Chiamo $ C_1 $ questo ciclo.
Inoltre anche all’interno di $ R_k $ esiste un ciclo che passa per $ T_{k} $ e $ S_k $, chiamo $ C_2 $ questo ciclo.
Per quanto detto se $ A \not \in C_2 $ allora $ T_{k}\in C_1 $.
Quindi esistono sicuramente due vertici o $ (T_k, S_k ) $ o $ (A,S_k) $ (o entrambi) t.c. appartengano sia a $ C_1 $ che a $ C_2 $ ed esiste un percorso che li connetta che appartenga sia a $ C_1 $ che a $ C_2 $.
Sia rinominato P il vertice (è facile verificare che è o $ T_k $ o A) che abbia la seguente proprietà: considerando solo il percorso comune a $ C_1 $ e $ C_2 $ è il vertice più distante da $ S_k $.
Rinomino $ S_k $ chiamandolo Q.

Step 5: esiste un ciclo di lunghezza pari.
Per come sono stati definiti $ C_1 $ e $ C_2 $ hanno solo un tratto in comune (solamente da P a Q).
Coloro di giallo il percorso in comune.
Coloro di verde il percorso appartenente solo a $ C_1 $ e di arancio il percorso appartenente solo a $ C_1 $.
Se la th fosse falsa sia $ C_1 $ che $ C_2 $ avrebbero sicuramente lunghezza dispari.
Se il percorso giallo (in comune) ha lunghezza pari allora i percorsi verde e arancio hanno lunghezza dispari e viceversa.
In entrambi i casi scegliendo il percorso verde + il percorso arancio ottengo un ciclo di lunghezza pari.

Hmm ... per induzione, no eh?

un mex di troppo

allora, come già detto c'è almeno un ciclo, adesso prendiamo un ciclo $ \mathbb{C} $ dal grafo : se ha lunghezza pari abbiamo finito altrimenti ha lunghezza dispari, prendiamo adesso tre vertici $ X,\ Y,\ Z $ che stanno tutti e tre sul cammino che costituisce il ciclo, osserviamo che se è possibile arrivare da $ X $ a $ Y $ senza percorrere lati che stanno su $ \mathbb{C} $ allora esiste un ciclo di lunghezza pari poiché detto $ \mathbb{C}_1 $ il nuovo cammino da X a Y allora o a lunghezza pari il cammino costituito dall'arco di $ \mathbb{C} $ contenente Z +$ \mathbb{C}_1 $ o ha lunghezza pari il cammino costituito dall'arco di $ \mathbb{C} $ NON contenente Z + $ \mathbb{C}_1 $ che sono entrambi cicli.

quindi se due punti stanno su un ciclo è possibile arrivare da uno all'altro solo percorrendo quello stesso ciclo e non con altri cammini.

Prendiamo quindi un punto $ A_1 $ che sta su $ \mathbb{C} $, definiamo adesso un nuovo grafo $ \mathbb{G}_1 $: se da $ A_1 $ si dipartono esattamente 3lati allora cancelliamo il lato che non unisce $ A_1 $ ad elementi di $ \mathbb{C} $ e chiamiamo $ \mathbb{G}_1 $ il grafo costituito da tutti i vertici non connessi a $ \mathbb{C} $ e dai lati che li uniscono, se da $ A_1 $ si dipartono più di 3 lati allora cancelliamo i due lati che uniscono $ A_1 $ a $ \mathbb{C} $ e chiamiamo $ \mathbb{G}_1 $ il grafo costituito da $ A_1 $ e tutti gli elementi connessi con$ A_1 $.

adesso osserviamo che neppure $ \mathbb{G}_1 $ può essere un albero poiché ance qui tutti i vertici hanno grado >1, adesso è sufficiente individuare un altro punto $ A_2 $ su $ \mathbb{G}_1 $ con grado >=3 (esiste necessariamente poiché $ \mathbb{G}_1 $ ha almeno tre vertici) e analogamete a prima individueremo un nuovo grafo $ \mathbb{G}_2 $...

poiché l'operazione potrebbe essere reiterata a piacimento si ha che il grafo dovrebbe avere infiniti vertici... assurdo.

Per essere pignoli, non c'è scritto grafo finito ... e sarebbe meglio aggiungerlo, visto che serve anche per avere almeno un ciclo ... i grafi con infiniti vertici e lati esistono, solo non si usano di solito nei problemi delle oli...
Per farvi un esempio, considerate tutte le parole fatte con le 4 lettere {a,b,c,d}, con la regola che le sequenze ac, ca, db, db "scompaiono", ovvero le parole "aaac", "aaca", "aabd", "aadb", "aa" sono uguali; usate queste come vertici e collegatene due se si possono ottenere l'uno dall'altro togliendo o aggiungendo una lettera a destra. Quello che avete ottenuto si chiama albero quadrivalente infinito; non ha cicli e ogni vertice ha valenza 4.