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
