Anticricche

[Anér]

Come al solito è facile, come al solito date la soluzione solo se non sapete risolverlo.
Abbiamo un grafo su n vertici, e ogni vertice ha grado minore o uguale a k. Dimostrare che si possono prendere almeno $ \lceil\frac{n}{k+1}\rceil $ vertici che formino un'anticricca (che siano dunque a due a due non collegati).

[Anér]

Come al solito date la soluzione solo se non sapete risolverlo.

Suvvia, era uno scherzo!

[Euler]

Ma sbaglio o è semplicissimo? Penso vada bene costruire l' anticricca facendo vertice per vertice. Prendo un vertice a caso, e questo sarà il primo appartenente all'anticricca; poi, per scegliere il secondo, ho una scelta di almeno $n-k-1$ altri vertici, visto che uno è il vertice stesso e al massimo altri k sono quelli a lui collegati, che nel peggiore dei casi non sono collegati a quello da scegliere. Poi procedo con il terzo, e dovrò sceglierlo almeno tra $n-2k-2=n-2(k-1)$, per gli stessi motivi. Ora posso dimostrare che l'm-esimo termine dell'anticricca lo posso scegliere tra almeno $n-(m-1)(k+1)$ vertici; infatti, se prima ne ho già scelti $m-1$, dovrò escluderne $(m-1)k$ e i vertici stessi.
Quindi adesso, per vedere quanti vertici può contenere al minimo l'anticricca, basterebbe che $n-(\lceil\frac{n}{k+1}\rceil-1)(k+1)$ sia maggiore di 0 (e non quello successivo). Questo è vero perché $\lceil\frac{n}{k+1}\rceil-1< \frac{n}{k+1}$ e sotituendo $\frac{n}{k+1}$ ottengo l'uguaglianza a 0 (mentre con l'intero subito dopo si ottiene un numero nullo o negativo) $\square$

[Anér]

Ma sbaglio o è semplicissimo?

No, non sbagli, era davvero semplice.