Forum de Mathématiques: Maths-Forum

Le théorème de Konig dit qu'un graphe est biparti s'il il n'y a pas de cycle de longueur impair.

Quelqu'un aurait-il une démonstration ?

Merci d'avance.

Donc si G est d-régulier de degré n et d impair. Alors il est impossible de construire un graphe d-régulier de degré n+1...Par le lemme des poignées de mains ça oblige que d et n ne peuvent etre simultanément impair. D'où ma conclusion.

Soit la propriété du prof est fausse. Soit je suis mal-barrée!

S'il n'a pas démontré c'est peut-être que ce n'était pas utile...Mais bon aussi étrange que cela puisse etre. Je retiens mon cours que par les démonstration, ça me permet d'etre convaincu...Et là ben c'est raté! lol Bonne soirée et merci, je vais aller prendre des force :dodo: . A bientot, et merci ...

Ben314 a écrit:Salut,
Tu as essayé pour n=3 et d=1 ?

Lol ça marche pas...où alors je ne vois pas! Pourtant la propriété a été citée en cours! (><)

houda 20 a écrit:bon par absurde,
on suppose qu'il existe n et d tel qu'aucun graphe d'ordre n n'est d-régulier
i.e
quelque soit le graphe d'ordre n, il existe tjrs un xi tel que d°(xi) est différent de d

J'ai pas vu, je me penche là dessus.

Merci!

Oui je veux dire d-regulier. En fait il a balancé ça juste après avoir définit un graphe régulier (tous les sommets ont même degré). En fait j'ai continué sur mon idée le fait d'introduire un sommet supplémentaire, ça ne change pas le nombre d’arêtes. Donc là je sais pas si ça va changer le d...si j...

Bonsoir dans mon cours j'ai: Tout couple de nombres naturels d et n tels que 0<=d<=n-1. Il existe un graphe régulier d'ordre n et de degré d. Mon prof a dit que la démo était trivial...mais bon pour moi pas =(. J'ai essayé par récurrence sur n, pour l'initialisation ça va. Mais ensuite...J'ai essayé...