Valakinek valami ötlete a bizonyításra?

Minden csúcshoz 1-esek és 2-esek szorzatát rendeljük, azaz a hozzárendelt számok mindegyike 2 hatvány.

Egyszerű gráf esetén a maximális fokszám n-1, és mivel összefüggő, ezért legalább 1.

Így a lehetséges szorzatok az 1, 2, 2^2, ... 2^(n-1) számok közül kerülhetnek ki, ez n-féle szám.

Már csak az van hátra, hogy nem fordulhat elő mind az n-féle egyszerre:

Tegnap volt ugyanez.

Ha van 2^(n-1) érték, az azt jelenti, hogy valamelyik csúcs mindegyik másikkal össze van kötve, és minden élre 2 van írva. Emiatt ekkor minden más csúcsnak van 2-essel jelölt éle. De ekkor nem szerepelhet az 1, mint szorzat.

Ha meg nincs 2^(n-1), akkor meg azért van legfeljebb (n-1)-féle érték.

Tehát legfeljebb (n-1)-féle érték szerepelhet az n csúcs esetén, s emiatt van kétszeresen előforduló érték.