Graphes:lien entre connexite et degre

[invitef55e92ca]

Bonjour a tous

j'ai une question a propos des graphes :
si G est un graphe d'ordre n (>1) et d(G) le degre minimum d'un sommet de G.
Alors je me demande comment prouver que si d(G) est superieur ou egal a la partie entiere (par valeur superieure) de n/2 alors G est connexe.

J'ai testé pour des petites valeurs de n :
n=2 : c'est le graphe trivial à 2 sommets (et chacun des 2 sommets est de degre 1) -->connexe
n=3 : "triangle" (3 sommets, 2 aretes chacun) ->connexe
n=4 : "carre" (avec ses diagonales) (au moins de 2 sommets chacun) ->connexe

Pour une idée de demonstration, j'avais pensé à faire une contraposee :
mq si G n'est pas connexe alors d(G)<E[n/2]
J'ai essayé avec n=3 :
1 _____ 2 _____ 3
Ce graphe satisfait bien l'hypothese : il n'est pas connexe, et le degré minimum du sommet 1 est 1<E[3/2]=2 (par valeur superieure)
Seulement, je n'arrive pas a generaliser : je n'arrive pas à trouver le point de depart (meme en essayant par recurrence). Il y a peut-etre une propriete sur les graphes qui serait utile ici (si oui je ne vois pas laquelle)

Est-ce que qq'un saurait m'eclairer ?

Merci beaucoup
-----

[invite6b1e2c2e]

Salut,

Tout simplement, s'il n'est pas connexe, il a au moins une composante connexe de taille <N/2. Est-ce qu'alors, ce n'est pas clair que d(G) < N/2 ?

__
rvz

[invitef55e92ca]

s'il n'est pas connexe, il a au moins une composante connexe de taille <N/2.

je suppose que la taille est le nbre d'aretes ...
mais comment est-ce que tu es certain qu'au moins une composante connexe sera de taille <N/2 (je le vois sur des exemples mais a-t-on le droit de l'affirmer (sans le montrer) ?)

desolee, c'est mes premiers exos en graphes....

[invite6b1e2c2e]

Non, N, c'est le nombre de sommets. Ce que je dis juste, c'est que s'il y a plus d'une composante connexe, alors il y en a au moins deux, donc il y en a forcément une avec moins de N/2 sommets. Sinon, tu trouverais trop de sommets !

__
rvz

[A voir en vidéo sur Futura]

[invitef55e92ca]

Merci rvz pour ces precisions !
Donc, en resume :

On suppose G non connexe.
Il a donc au moins 2 composantes connexes, et l'une des deux est forcement de taille < ou = à N/2 (en effet, si elles etaient toutes les 2 de taille > à N/2, alors le graphe aurait un nbre de sommets > à (N/2)+(N/2)=N -> impossible car G est d'ordre N) (->est-ce que c'est correct ?)

Est-ce qu'alors, ce n'est pas clair que d(G) < N/2 ?

pas vraiment... On a mq le degré d'une composante de G est inferieur a N/2, mais comment montrer que le degre du graphe est lui-meme inferieur a N/2 ?

Merci d'avance

[invitefe509ad8]

Souviens toi de la définition du degré du graphe : c'est une propriété vérifiée sur chacun de ses sommets, non ?
Si cette propriété est vraie pour chacun de ses sous ensembles, l'est-elle pour le graphe tout entier ?

[invitef55e92ca]

Je m'egare, en fait il faut considerer le degre minimum de G (soit le degre minimum d'un sommet de G)

si G est un graphe d'ordre n (>1) et dmin(G) le degre minimum d'un sommet de G.
comment prouver que si dmin(G) est superieur ou egal a la partie entiere (par valeur superieure) de n/2 alors G est connexe.

On a mq si G est non connexe alors il y a au moins une composante connexe du graphe de degre < à N/2; et là comment pourrai-je montrer que dmin(G)<N/2 ?

la définition du degré du graphe :

d(G)=somme des degres de chaque sommet de G
=2*nbre d'aretes,
seulement, je n'arrive pas à me servir de cette propriété...

J'aimerais bien trouver et comprendre cette demo, pouvez-vous me donner un coup de main supplementaire svp

Merci d'avance