Question

Imi poate explice cineva pe larg de ce este 29?

Answer 1

Pentru a fi siguri ca graful cu 9 noduri e conex trebuie sa luam cazul cu cele mai multe noduri, cazul cel mai extrem. Si acest caz apare cand 8 noduri sunt complet legate intre ele unele de celalalte (subgraf complet) si inca o muchie care sa lege ultimul nod de oricare alt nod din cele 8. Astfel indiferent de modul in care sunt puse muchiile graful e conex.

Deci trebuie sa  avem muchii suficiente pentru un subgraf de 8 noduri complet plus inca o muchie.

Numarul de muchii intr-un graf complet cu 8 noduri : 8*7/2 = 28 muchii

28+1 = 29.

E destul de greu de explicat, poate ca o explicatie vizuala ar fi mult mai buna... Totusi sper ca te-a ajutat raspunsul meu