OliForum Matematico

Scusate la domanda forse stupidissima (di combinatoria non so molto... ). Nella soluzione del problema C5 del preIMO 2008, Gobbino (è lui, vero?) dice che si può dimostrare facilmente con double-counting che in un grafo i vertici da cui parte un numero dispari di lati sono per forza in numero pari. Come si può fare?

Praticamente ti conti la somma del numero di lati che esce da ciascun vertice al variare dei vertici, e così conti esattamente due volte(double counting) ciascun lato...quindi quella somma è pari(2 volte il numero di lati), quindi i vertici da cui esce un numero dispari di lati devono essere in numero pari.

Ah, ok... Che scemo Grazie mille!

Anche induzione sul numero di lati, eh...