Grafi connessi

red3
Spero di non aver sbagliato la collocazione di questo quesito, che propongo:
Supponiamo di avere un Grafo (non orientato) G connesso. In G tutti i nodi sono di grado pari. E' vero o falso che togliendo un lato qualsiasi il grafo G' ottenuto resta connesso?
PS:Mi riservo di dare la mia idea alla fine della discussione

Risposte
Studente Anonimo
Studente Anonimo
In un qualsiasi grafo semplice, siccome ogni lato tocca esattamente due vertici, la somma dei gradi dei vertici è due volte il numero di lati.

Se tu potessi disconnettere il tuo grafo togliendo un lato allora nel grafo G' così ottenuto prendi una componente connessa H; tutti i gradi dei vertici di H tranne uno sono pari. Ma allora la somma dei gradi dei vertici di H è dispari, assurdo.

red3
Intanto grazie per la risposta, attendo altre idee, poi esporrò la mia

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.