Valakinek elképzelése a megoldásról?

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:

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.

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.

Ennyi.

Ha pedig nincsen 2^(n-1)-es érték, akkor az hiányzik, és ezért nincsen n féle érték.

Teljességre ügyeljünk. :) (egyébként ment a plussz, első, szép indoklás, a lényeg benne volt, csak gondoltam kiegészítem.)