Forum de Mathématiques: Maths-Forum

Bonjour On peut faire une récurrence sur le nombre de composantes connexes mais il faut bien formuler l'hypothèse : Supposons que pour tout graphe qui a k composantes connexes , on peut le rendre connexe en lui ajoutant k-1 arêtes convenablement choisies , mais on ne peut pas le rendre connexe en l...

bonjour, du graphe G , on peut en déduire un graphe G' à k sommets , chaque sommet de G' étant une composante connexe de G. G' est discret,il a k composantes connexes réduites à un point. Pour le rendre connexe, il faut donc ajouter k-1 arêtes. Ensuite G' est connexe si et seulement si G est connex...

Bonjour, Bonsoir,

Soit un graphe G = (V,E) avec k composantes connexes.
Je souhaite rendre le graphe connexe, il faut donc ajouter exactement k - 1 arêtes.

Mais je n'arrive pas à prouver ça de manière formelle, si quelqu'un a une piste je suis preneur !

Merci d'avance !