Grafi che hanno quadrati con due lati

[karlosson_sul_tetto]

Sia dato un grafo con $n\geq 4$ vertici. Determinare in funzione di $n$ il numero minimo di lati che deve avere affinché sia rispettata la seguente condizione: in qualunque modo si scelgano 4 vertici, tra essi sono presenti almeno due lati (ovvero, ci sono almeno due lati che collegano due di questi quattro vertici).

[Troleito br00tal]

Ma dobbiamo trovare il numero minimo di lati che può avere il grafo o il numero minimo di lati che deve avere il grafo?

[karlosson_sul_tetto]

Direi il numero minimo che può avere, anche perché l'altro caso mi sembra più facile, se il mio naso non m'inganna

[Troleito br00tal]

Sì infatti basta toglierne 4 da un quadrato XD