OliForum Matematico

Dimostrare che un grafo finito connesso di mindegree k (ovvero tutti i vertici hanno almeno k vicini) avente un numero sufficientemente elevato di vertici (diciamo V(k)), ha una partizione $ V_1,V_2 $ dei vertici tale che i grafi indotti da questi due insiemi siano almeno di mindegree (k-1).

Giusto per dar credito al fatto che anche i matematici hanno una vita sociale e postano alle 23.30 il sabato sera del ponte di ferragosto e chi piu' ne ha piu' ne metta...

Considero un grafo completo con 5 vertici (quindi k=4).

Tra le sue 2 partizioni $ V_1,V_2 $ ce ne sarà almeno una con o 2 o 1 vertice.

Il grafo indotto da questa partizione ha mindegree $ \leq 1 $.
Ma se la tesi fosse vera dovrebbero avere mindegree $ \ge k-1=3 $.

Forse ho frainteso il problema..oppure manca qualche ipotesi?

In effetti manca un lowerbound sul numero di vertici...
ora sistemo (non si puo' pretendere la lucidita' a mezzanotte il sabato sera... )

Prendo due copie di $ \displaystyle \mathbb{Z}_n $, in ciascuna copia collego ciascun elemento con il successivo e con il precedente, inoltre collego ciascun elemento della prima copia con il corrispondente e con il successivo della prima copia.
Ottengo un grafo 4-regolare connesso, arbitrariamente grande.
Mettiamo che ho una partizione (A,B) come dici tu. Un triangolo deve stare completamente dentro A o B, altrimenti trovo un vertice che ha due archi che scappano dall'altra parte, e quindi gli restano al massimo due dalla sua, troppo pochi. Ma se ogni triangolo sta completamente in A o in B, da come è fatto il grafo esibito prima si vede subito che uno tra A e B è vuoto.

Ora, se Catraga è ancora vivo (speriamo!) e si ricorda cosa aveva in mente quel lontano sabato sera potrebbe aggiungere qualche altra ipotesi