Bonsoir,
Pour mon DM de Theorie des Graphes, je bloque sur la derniere partie de cette exo:
1. Montrez qu'un graphe connexe avec au moins autant d'arêtes que de sommets doit contenir un cycle.
2. Soit G un graphe connexe à n sommets et m arêtes pour n 2. Montrer que G contient un sous-graphe biparti H: = H (V; E) avec V (H) = V (G) et |E(H)| m/2
3. Soit K un graphe connexe avec n sommets et au moins 2n - 1 arêtes pour n 2. Montrer que K contient un cycle de longueur paire.
Alors j'ai montrer 1 et 2 mais pour 3, voila mon idee: K est connexe donc on pourrait appliquer 1 et déclarer qu'il contient un cycle. Ensuite, appliquer 2 à K et déclarer qu'il contient aussi un sous-graphe biparti, mais je ne peux pas simplement affirmer que mon cycle est dans le sous-graphe biparti et devrai le prouver? C'est pourquoi j'ai aussi pensé à appliquer d'abord 2 pour dire que j'ai un sous-graphe biparti dans K puis utiliser 1 sur le sous-graphe biparti, cependant je ne peux utiliser 1 que lorsque le graphe est connexe, or est-ce que le sous-graphe biparti de mon graphe K est également connexe? Du coup j'ai donc pensé à considérer les parties connexes du sous-graphe biparti de K mais je ne suis pas sûr que celles-ci respectent la condition sur le nombre minimum d'arêtes.
Des idees ? Merci d'avance !
BonsoirGBZM
Oui tout a fait ! C'est justement la propriete que je conte utiliser mais comment montrer que mon cycle est effectivement dans le sous-graphe biparti de K ?
Je crois que ca ne l'est pas forcement, c'est pourquoi j'ai pensé à considérer les parties connexes du sous-graphe biparti de K (mais je ne suis pas sure comment)
Pardon je voulais dire sommets. J'ai suppose que le resultat est vrai pour un graphe avec moins de n sommets. Maintenant choisissons un sommet v de G, et soit A le graphe obtenu à partir de G en supprimant v et toutes les arêtes de G incidentes en v. Si d = deg (v), | E (A) | = | E (G) | - d. Par l'hypothèse de récurrence, A a un sous-graphe biparti H avec au moins | E (A) | / 2 arêtes; soit V1 et V2 les ensembles de sommets de ce sous-graphe. On peut supposer que V1∪V2 = V (H), c'est-à-dire que H garde tous les sommets de A. Maintenant il suffit d'ajouter v à V1 ou à V2 tout en decidant laquelle des d arêtes de G incidentes à v garder pour obtenir un sous-graphe biparti de G avec au moins | E (G) | / 2 arêtes.
Et le graphe biparti que tu construis ainsi ne serait-il pas automatiquement connexe, si le graphe G de départ l'est ?
Je vois, donc est-ce suffisant comme justification de dire que mon sous-graphe biparti est "automatiquement" connexe?
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :