Bonjour (ou bonsoir). J’espère être au bon endroit pour poster ceci..
J’ai une idée pour raccourcir de manière assez significative la fin d’une longue démonstration du cours de théorie des graphes, et j’aimerais savoir si elle est valable (pour un examen oral par exemple). Il s’agit de la démonstration du corollaire II.2.6 , pages 75 et 76 du cours (spectre symétrique implique graphe biparti).
Contexte :
Nous avons notamment montré que les ensembles V1 et V2 sont disjoints, et que tout chemin reliant un sommet de V1 à un sommet de V2 est nécessairement de longueur impaire. Pour conclure la preuve, au dernier paragraphe (“Supposons à présent que, dans G,un chemin…”) , il reste à montrer que 2 sommets de V1 (et V2 mais preuve identique) sont forcément reliés par des chemins de longueur paire. Ce qui est développé dans les feuilles est assez long et compliqué, et j’ai pensé à ceci.
J’aurai besoin de
(1) Les sommets de V1 (resp. V2) sont reliés à u par un chemin de longueur impaire (resp paire).
(2) V1 et V2 sont disjoints.
Soient a et b des sommets de V1. Vu (1) , a est joint à u par C1 de long. impaire , b à u par C2 de long. impaire. Procédons par l’absurde et supposons que a et b sont joints par un chemin de long. impaire C3. Alors le chemin qui part de u, prend C1 puis C3 et arrive à b est de long. paire (impaire+impaire = paire). Vu (1), on obtient que b appartient aussi à V2 , d’où contradiction vu (2). (de meme, a est dans V2 aussi).
Donc a et b sont forcément joints par un chemin de longueur paire , ce qui conclut.
Serait-il possible que vous confirmiez si cela est correct s’il vous plait ?
Merci d’avance.
Adrien Deliège , 2 BM
——————————
Tout d’abord un commentaire général : lors d’un examen oral, je suis ravi de pouvoir discuter avec un étudiant de preuves alternatives ou de variantes aux démonstrations présentées. En effet, le plus intéressant pendant l’examen est de savoir si les étudiants ont réfléchi et muri les concepts développés aux cours. Donc, même si un étudiant me proposait à un oral une preuve originale mais inexacte, il serait alors très intéressant de discuter avec lui pour sortir de l’examen avec une nouvelle preuve correcte. (Bien sûr, je comprends très bien que dans l’immense majorité des cas, on reprenne la preuve vue au cours).
Bon, à présent pour ce qui est spécifiquement de l’argument proposé. Il me paraît tout à fait valable et est d’ailleurs basé sur le même genre d’argument que celui développé dans le cours. Donc, cela me convient très bien.
Publié par michelrigo 
