Chaque graphique simple non orienté avec plus de

Si un graphique avec $n$ sommets a plus de $\frac{(n-1)(n-2)}{2}$ bords puis il est connecté.

Je suis un peu confus à propos de cette question, car je peux toujours prouver que pour un graphique connecté, vous avez besoin de plus de $|E|>n-1$ bords.

Je ne sais pas ce qui vous dérange mais comme je le vois, vous êtes confus au sujet des deux faits suivants

1. Si un graphique est connecté, $e \geq n-1.$

2. Si un graphique a plus de $e > \frac{(n-1)(n-2)}{2}$ alors il est connecté.

Notez que les implications en 1 et 2 sont dans des directions opposées.

Pour une preuve de 2. vous pouvez consulter ce lien .

Je pense que votre problème pourrait être de prouver que vous ne pouvez pas construire un graphique non orienté avec$\dfrac{(n-1)(n-2)}{2}$bords non connectés. Vous y pensez dans le mauvais sens. le$E = n - 1$ formule sur le nombre d'arêtes que vous pouvez utiliser pour connecter tous les sommets.

Imaginez que vous êtes un adversaire essayant de concevoir un horrible réseau routier afin qu'une ville soit déconnectée. Peu importe la façon dont vous dépensez vos routes de manière inefficace, vous devrez toujours relier toutes les villes s'il y a tant de routes.

Réfléchissez à la pire conception possible, par exemple celle qui utilise autant de routes que possible mais qui laisse une ville déconnectée. Combien d'arêtes cela a-t-il? Que se passe-t-il lorsque vous ajoutez un avantage supplémentaire à cela?

1.Comme vous l'avez mentionné, nous avons:

$G\text{ is connected} \Rightarrow |V|-1 \le |E|$

Mais l'autre sens n'est pas vrai, c'est-à-dire:

$G\text{ is connected} \Leftrightarrow |V|-1 \le |E|$

est une mauvaise déclaration.

Vous ne pouvez donc pas l'utiliser pour un raisonnement supplémentaire. Un exemple de compteur est ce graphique ($K_t$ est un graphique complet sur $t$ sommets, et $\cup$ signifie union disjointe de graphes):

$G = K_{n-1} \cup K_1$

$G$a arêtes et nœuds, et pour .$n-1\choose 2$$n$${n-1\choose 2} > n-1$$n>4$

2.D'autre part, prouver que:

${|V|-1 \choose 2} < |E| \Rightarrow G\text{ is connected}$

Nous pouvons le faire comme suit:

Supposons que non, alors est l'union disjointe de deux graphes , avec , si nous connectons tous les sommets de ensemble pour faire le graphe , alors (car a au plus comme arêtes complètes du graphique) mais:$G$$G=G_1\cup G_2$$|G_1| = k, |G_2| = n-k, 0<k<n$$G_1,G_2$$G"$$|E_{G"}|\le {n \choose 2}$$G"$

${n-1 \choose 2} + 1 + k\cdot (n-k) \le |E_{G"}| \le {n \choose 2} \Rightarrow$

$(k-1)(n-k-1) + 1 \le 0\Rightarrow$ Contradict avec .$0<k<n$

Le graphe G a n nœuds n = (n-1) +1 Un graphe à déconnecter doit comporter au moins un sommet isolé. Un graphe avec un sommet isolé a un maximum de C (n-1,2) arêtes.

donc chaque graphe connecté doit avoir plus de C (n-1,2) arêtes.