Megoldás: 11.5
Továbbra is érdemes a
11.1M2. megoldásának gondolatát használni. Gráfok esetében azt kapjuk, hogy ha az
x csúcson a minimális szám áll, továbbá az
x és
y csúcs között van út a gráfban, akkor ugyanannak a számnak kell állnia rajtuk, tehát a gráf egy komponensének összes csúcsán ugyanaz a szám áll. Összes csúcsa megszámozásához legfeljebb annyi számot használhattunk, ahány összefüggő komponensre bomlik a gráf.