Teorema Dilworth-like per i grafi

[Tibor Gallai]

Dato un grafo G, sia $ ~\alpha (G) $ il massimo numero di suoi nodi a due a due non adiacenti.
Mostrare che i nodi di G possono essere partizionati in al più $ ~\alpha (G) $ classi in modo che, se una classe ha più di 2 elementi, questi formino un ciclo in G. Inoltre, se una classe ha esattamente 2 elementi, essi devono essere adiacenti in G.

[Tibor Gallai]

Forse la parola "Dilworth-like" ha spaventato qualcuno... In realtà non serve sapere il teorema di Dilworth per risolvere il problema, né è molto utile sapere la sua dimostrazione. E' solo che le tesi si somigliano un pochino, ma la somiglianza finisce qua.

Dò un hint: mostrare che G contiene un sottografo H della forma voluta (un ciclo, una coppia di nodi uniti, un nodo isolato), in modo che esista un nodo di H che ha vicini solo in H e non nel resto del grafo.

[piever]

Uhm, il mio iniziale proposito di farlo senza guardare l'hint è fallito miseramente: a questo punto, tanto vale scrivere la dimostrazione l'esistenza di H...

Prendo un punto a caso nel grafo. Lo chiamo $ P_1 $ e lo coloro di rosso. Poi passo a un vicino a caso di $ P_1 $ (che non sia già rosso), lo coloro di rosso e lo chiamo $ P_2 $. Poi passo a un vicino di $ P_2 $ (che non sia già rosso), lo coloro di rosso e lo chiamo $ P_3 $ e così via...

A un certo punto arriverò a un $ P_n $ tutti i vicini del quale sono rossi. Sia $ P_k $ il suo vicino con l'indice più piccolo. L'insieme $ H=\{ P_k,\dots ,P_n\} $ funziona (il punto che non ha vicini esterni è $ P_n $)

[Tibor Gallai]

Yesss!
Hai ragione sull'hint, volevo darne uno meno incisivo, ma non avevo idee.