Problemino sui grafi

[Karl Zsigmondy]

Sia G un grafo tale che la valenza/il grado di ogni vertice (il numero di archi uscenti da ogni vertice) sia maggiore o uguale a 3. Allora G contiene almeno un ciclo di lunghezza pari.

[EvaristeG]

Forse un grafo finito (anche se probabilmente per molti sta dentro la definizione di grafo)

[Karl Zsigmondy]

Forse un grafo finito (anche se probabilmente per molti sta dentro la definizione di grafo)

Sisi, finito!

[Tess]

È un esercizio carino! E non difficile!
Mi auguro che qualcuno con non molta esperienza si cimenti a risolverlo!

Ah, piccolo hint generale:

Testo nascosto:

Problema coi grafi $\rightarrow$ induzione, magari estesa.
Bisogna solo capire su cosa fare induzione...

[Chuck Schuldiner]

Bagonzo io invece avevo seguito un'altra strada

Testo nascosto:

se per assurdo i cicli son tutti dispari, come sono disposti tra loro? e che succede se uccido tutti gli archi che compongono quei cicli?

[Tess]

È vero, forse si può fare tutto in una volta!
Però, guardando sotto un punto di vista diciamo più formale,

Testo nascosto:

fai un'induzione in cui il passo induttivo è proprio quello che dici!

[machete]

Esiste almeno un ciclo. Inizio a camminare da un punto a caso e segno i vertici su cui passo, dato che ogni volta che entro in un vertice ho almeno due modi per uscirne, ed essendo il grafo finito, dopo un po' passo per un vertice già segnato, quindi ho trovato un ciclo.

Considero due vertici a caso nel ciclo, diciamo A e B. Se esiste un cammino AB* che porta da A a B diverso da quello del ciclo ho vinto, infatti se la distanza sul ciclo fra A e B è pari e AB* è dispari posso a cambiare (passando per AB*) la parità del ciclo iniziale, se è pari passo per A e B sul ciclo iniziale e poi percorro AB*. Il caso in cui la distanza AB sul ciclo sia dispari è analogo.

Supponiamo ora che partendo da ogni vertice non si possa mai raggiungerne un altro. Prendo un vertice V e separo i vertici in X (i vertici raggiungibili da V) e Y (i vertici non raggiungibili da V ) chiaramente X ed Y non sono vuoti e non posso raggiungere un elemento di X da uno di Y. In X U {V} c'è almeno un ciclo (anche se V ha grado esattamente 3, lo si dimostra come prima) a questo punto ho tutte le ipotesi che avevo sul primo ciclo che è distinto da questo. Se anche i vertici del nuovo ciclo non sono mai raggiungibili ne scelgo uno diverso da V e riapplico lo stesso ragionamento, che chiaramente non può essere portato avanti all'infinito perché sto separando i vertici in infiniti sottinisiemi disgiunti.

Sarà vero?

[Tess]

Servirebbe un po' più di formalità. In particolare non capisco bene l'ultimo paragrafo:

Supponiamo ora che partendo da ogni vertice non si possa mai raggiungerne un altro

Stai considerando da "vertice nel ciclo" a "vertice nel ciclo"? Se no, non vedo che vuol dire... Se sì, devi spiegare meglio anche il resto del paragrafo!

Quando alla fine parli di un ragionamento "che non può essere portato avanti all'infinito", direi che è arrivata l'ora di usare il termine "induzione".

Se la riscivi, vedrò di rispondere alla tua domanda!

[machete]

Sì in effetti sono stato frettoloso. . . vediamo di far meglio:

Lemma: Se in un grafo finito ogni vertice ha grado maggiore o uguale a due allora esiste almeno un ciclo.

dim. Inizio a camminare da un punto a caso e segno i vertici su cui passo, dato che ogni volta che entro in un vertice su cui non sono stato ho almeno un modo per uscirne, ed essendo il grafo finito, in un numero finito di passi arrivo in un vertice già segnato, quindi ho trovato un ciclo.

In particolare nel nostro problema esiste un ciclo $ c $. Se questo ciclo è pari ho finito, supponiamo sia dispari e distinguiamo due casi:

(i) Esistono due vertici $ A,\ B $ su $ c $ tali che esiste un cammino diverso da quello per $ c $ che li congiunge. Sia $ AB^* $ tale cammino e $ AB $ quello su $ c $. A questo punto se $ AB $ e $ AB^* $ hanno la stessa parità ho trovato un nuovo ciclo di lunghezza pari, se invece hanno parità diverse considero il ciclo $ c $ solo che invece di passare per $ AB $ passo per $ AB^* $, in questo modo ottengo un ciclo che ha parità diversa da quella di $ c $, cioè è pari.

(ii) Comunque io scelga una coppia di vertici $ A,\ B $ su $ c $ non esiste un percorso (diverso da $ c $ stesso) che li congiunga. Consideriamo quindi un qualsiasi vertice $ V $ di $ c $. A questo punto divido l' insieme dei vertici del mio grafo in due sottinsiemi $ X, Y $. In $ X $ metto i vertici che sono raggiungibili da $ V $ senza passsare per $ c $, in $ Y $ metto i vertici che sono raggiungibili da $ V $ solamente passando per $ c $. Dato che $ V $ ha grado $ \geq 3 $ posso muovermi da questo vertice senza stare su $ c $ quindi $ X $ è non vuoto. In $ Y $ ci sono per ipotesi almeno i vertici di $ c $ diversi da $ V $. Osserviamo poi che nessun elemento di $ X $ sta in $ Y $, altrimenti potrei connettere due vertici di $ c $ senza passare per $ c $ stesso.

A questo punto considero il grafo che ha come vertici $ X\cup \{ V\} $ e come archi gli archi del grafo iniziale tranne quelli che collegavano $ V $ a $ c $. Se il grado di $ V $ nel nuovo grafo è esattamente $ 1 $ tolgo $ V $ e posso applicare il Lemma per trovare un nuovo ciclo (interno a $ X\cup \{ V\} $), se il grado di $ V $ è maggiore di $ 1 $ applico subito il Lemma. Ho quindi trovato un nuovo ciclo $ c' $ contenuto in un sottoinsieme proprio dei vertici e degli archi del grafo iniziale.

A questo punto non so quale sia il modo migliore per concludere (sempre se si può concludere) ma io direi così:

Mi sono ricondotto al problema iniziale: se per $ c' $ non si verifica il caso (i) posso scegliere un nuovo vertice $ V'\neq V $ di $ c' $ da cui fare lo stesso ragionamento, e costruire un nuovo ciclo $ c'' $ strettamente contenuto in $ X\cup \{ V\} $. In ogni passaggio però considero un sottoinsieme proprio del grafo precedente e tale inclusione non può andare avanti all' infinito.

Probabilmente c'è un modo più rapido ed elegante per farlo (con un' induzione azzecata forse?) ma ci tenevo comunque a sapere se questo ragionamento regge!

[Tess]

Diciamo che fin prima della "conclusione" va bene.
Io la conclusione l'avevo pensata via induzione non su tutti i grafi con tutti i vertici di grado almeno 3, ma su i grafi cheper un vertice hanno grado almeno 2 e gli altri con grado almeno 3. A questo punto "rifare il ragionamento" si traduce in un "ricondursi ad un'ipotesi induttiva" (e l'induzione sarebbe ovviamente estesa).
Quello che potrebbe sembrar strano è il passo base: grafi troppo piccoli infatti, non hanno quella proprietà. Il passo base potrebbe essere il $K_4$.

[Karl Zsigmondy]

Comunque si finisce così, manca poco!

Non so se quest'altra è giusta, ma mi torna più o meno ed è un pochino diversa. Potete dare un parere (vedere se è giusta) se volete.

Testo nascosto:

Sia k il numero totale di archi presenti in G.

LEMMA 1
Posso considerare wlog G connesso.
Dimostrazione: se non lo è, le sue componenti connesse hanno tutte vertici con grado maggiore uguale a 3 e mi rivolgo a quelle.

LEMMA 2
Ogni grafo G connesso ha al suo interno uno spanning tree (è possibile eliminare alcuni vertici di G facendo sì che rimanga solo un albero).
Dimostrazione: è nella lezione C2 medium del senior 2009, se volete posso metterla.

LEMMA 3
Il numero C di cicli presenti nel grafo è tale che: $ C \leq \frac{k}{3} $.
Dimostrazione: se due cicli dispari condividono un arco allora si può vedere che abbiamo un ciclo pari. Quindi i cicli dispari sono tutti disgiunti, e dal momento che sono lunghi almeno 3, il loro numero non può essere superiore a k/3.

LEMMA 4
Il numero C di cicli presenti nel grafo è tale che: $ C \geq k-(n-1) $
Dimostrazione: per il lemma 2 il grafo G ha al suo interno uno spanning tree, che ha per definizione n-1 archi. Se parto dallo spanning tree di G e aggiungo archi fino ad ottenere proprio G, per ogni arco che aggiungo fino ad arrivare a k creo almeno un nuovo ciclo, dal momento che unisco due vertici già precedentemente connessi da un altro cammino. Quindi creo almeno k-(n-1) cicli se G ha k archi.

Ora, per i lemmi 3 e 4 ho $ k-n+1 \leq C \leq \frac{k}{3} $ da cui segue che $ k \leq \frac{3n-3}{2} $. Ma dato che ogni vertice ha grado almeno 3 si ha che $ k \geq \frac{3n}{2} $, che è assurdo.

[Gottinger95]

@Karl Zsigmondy: la dimostrazione funziona. Bella, molto pulita!