Grafi che hanno quadrati con due lati
- karlosson_sul_tetto
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Grafi che hanno quadrati con due lati
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).
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: Grafi che hanno quadrati con due lati
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
- Messaggi: 1452
- Iscritto il: 10 set 2009, 13:21
- Località: Napoli
Re: Grafi che hanno quadrati con due lati
Direi il numero minimo che può avere, anche perché l'altro caso mi sembra più facile, se il mio naso non m'inganna
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
---
"Chissa se la fanno anche da asporto"
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: Grafi che hanno quadrati con due lati
Sì infatti basta toglierne 4 da un quadrato XD