Problemino sui grafi

[Catraga]

Sia G un grafo connesso con grado dei vertici medio maggiore di 2.
<BR>Dimostrare che contiene almeno due cicli.
<BR>

[FrancescoVeneziano]

Nessuno lo risolve? impegnatevi, sfaticati!
<BR>
<BR>Ricordo per chi l\'avesse dimenticato che il grado di un vertice è il numero di lati che partono da quel vertice.
<BR>
<BR>CaO
<BR>Francesco

[Catraga]

Suvvia...non e\' difficile...possibile che ogni volta che propongo un esercizio di teoria dei grafi nessuno si faccia avanti??!!!

[Sciankaman]

Cos\'è un grafo??[addsig]

[Catraga]

Un grafo e\' costituito da un insieme di punti ed un insieme di archi, ovvero segmenti che uniscono due punti.
<BR>Un quadrato e\' un grafo se si considerano i vertici come punti e i lati come archi.

[cekko]

rispondo perché mi sento chiamato in causa da FrancescoVeneziano <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>il grado dei vertici medio è >2.
<BR>se ci sono n vertici, ci saranno almeno n+1 lati.
<BR>non ci sarebbero cicli se ci fossero esattamente n-1 lati.
<BR>quindi c\'è almeno un ciclo.
<BR>tolgo un lato che fa parte del ciclo. nessun vertice si \"isola\". rimangono almeno n lati.
<BR>c\'è almeno un altro ciclo.<BR><BR>[ Questo Messaggio è stato Modificato da: cekko il 07-06-2004 19:42 ]