OliForum Matematico

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.

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

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

Sisi, finito!

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

Ah, piccolo hint generale:

Bagonzo io invece avevo seguito un'altra strada

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

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?

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

machete ha scritto: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!

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!

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$.

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.

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