Étape 1
Modélisons la situation : le réseau est représenté par un graphe simple non orienté $G = (V, E)$ d'ordre $n = 8$, où chaque sommet représente un serveur et chaque arête représente une liaison directe. La contrainte de l'administrateur signifie que pour tout sommet $v$, le degré vérifie $\deg(v) \ge k$.
Étape 2
Étudions le cas $k = 3$ en cherchant un contre-exemple.
Considérons un graphe $G$ composé de deux composantes connexes disjointes, chacune étant un graphe complet à $4$ sommets (noté $K_4$).
Dans chaque composante $K_4$, chaque sommet est relié aux $3$ autres sommets du même groupe, donc son degré est égal à $3$.
Le nombre total de sommets est $4 + 4 = 8$.
Cependant, il n'existe aucune arête reliant les deux composantes : le graphe $G$ n'est pas connexe.
Par conséquent, la condition $k = 3$ ne suffit pas à garantir la connexité du réseau.
Étape 3
Démontrons que la condition $k = 4$ garantit la connexité.
Raisonnons par l'absurde en supposant que chaque sommet a un degré vérifiant $\deg(v) \ge 4$ et que le graphe $G$ n'est pas connexe.
Si $G$ n'est pas connexe, il possède au moins deux composantes connexes disjointes $C_1$ et $C_2$.
Soit $v$ un sommet appartenant à $C_1$. Comme tous les voisins de $v$ doivent appartenir à $C_1$ et que $\deg(v) \ge 4$, la composante $C_1$ contient au moins le sommet $v$ et ses $4$ voisins, c'est-à-dire au moins $1 + 4 = 5$ sommets.
De la même façon, la composante $C_2$ contient également au moins $5$ sommets.
Le nombre total de sommets dans le graphe $G$ serait alors au moins égal à :
$$5 + 5 = 10$$
Or, le graphe est d'ordre $n = 8$, ce qui est impossible car $10 > 8$.
Étape 4
L'hypothèse selon laquelle $G$ n'est pas connexe pour $k = 4$ est donc fausse.
La valeur minimale de l'entier $k$ garantissant que le réseau est connexe est $4$.
Méthode clé
Pour déterminer un seuil critique $k$ garantissant une propriété théorique sur un graphe, on exhibe un contre-exemple pour $k-1$ puis on démontre la propriété pour $k$ (souvent par l'absurde).
Piège à éviter
Penser que $k=3$ suffit en sous-estimant la possibilité de former deux blocs totalement disjoints de 4 serveurs chacun.
