Théorie des graphes : 4 démonstrations ?

J'ai énormément de mal à savoir par où commencer les deux dernières démonstrations…

Indications:

-pour la 3, chaque graphe connexe a la propriété qu'il existe au moins un sommet tel que si on l'enlève, on obtient encore un graphe connexe

-pour la 4, tu prends un sommet et regardes le graphe composé de l'ensemble de ses non voisins

pardon

3 mais c'est pour tinviter à la prouver justement cette propre

Tu peux aussi enlever des arêtes jusqu'à plus possible sans déconnecter le graphe. Puis tu en enlèves une de plus deconnectante..

Bonjour,
Pour la 4, je te conseille d'utiliser le principe du Pigeonhole (si on doit répartir n+1 pigeons parmi n cages, alors au moins 1 cage contient au moins 2 pigeons).

Je donne des indications de démonstrations. Ces quatre faits sont à la base de n'importe quel cours élémentaire de théorie des graphes.

1. Montrez qu'un graphe simple a un nombre pair de sommets de degré impair. J'ai ma petite idée : je pense utiliser la formule "la somme des degrés d'un graphe = 2*card(ensemble des arêtes)" en séparant la somme des degrés de sommets à degrés impairs de la somme des degrés de sommets à degrés pairs… mais je ne vois pas trop comment.

C'est en effet l'idée qu'il faut utiliser. Séparer dans la somme les degrés pairs des degrés impairs. Et utiliser "pair + impair = impair", "impair + impair = pair".

2. Démontrez le Lemme de Koenig. Pour rappel, il dit qu'il existe nécessairement une chaîne élémentaire entre deux sommets s1 et s2 reliés par une chaîne quelconque. C'est tellement intuitif que c'en devient impossible à démontrer…

Si une chaîne qui relie les sommets existe, il suffit d'en prendre une de longueur minimale : elle conviendra. Si cette chaîne n'était pas élémentaire un même sommet apparaîtrait deux fois, d'où la présence d'une cycle que l'on pourrait enlever en faisant décroître la longeur de la chaîne.

3. Démontrez que G connexe comporte au moins card(ensemble des sommets) - 1 arêtes.

On pourrait faire une démonstration par récurrence utilisant le fait qu'un graphe connexe possède un sommet tel que si on l'enlève ainsi que les arêtes adjacentes, le graphe obtenu reste connexe. Mais ce resultat est plus compliqué à démontrer.

Il faut s'inspirer de ça pour faire une démo plus élémentaire, toujours par récurrence. Pour passer du cas de n sommets à n+1 sommets, on raisonne comme suit. Si le graphe possède un sommet de degré 1, alors on peut l'enlever ainsi que l'arête adjacente et ce qui reste est connexe. On applique l'hypothèse de récurrence. Sinon tous les sommets sont de degrés >=2 et on écrit l'équation "(somme des degrés)/2 = nbre d'arêtes" et on s'en sort sans utiliser l'hypothèse de récurrence.

Si on connait bien les arbres on a une autre démo comme suit :

-- un arbre sur n sommets possède n-1 arêtes
- - tout graphe connexe possède un arbre couvrant.

Le résultat en découle trivialement.

4. Démontrez qu'il n'existe pas de graphe non-orienté ayant au moins deux sommets et tel que tous les sommets aient des degrés distincts.

Noter que les degrés possibles varient de 0 à n-1, où n est le nombre de sommets. S'ils était tous distincts chaque valeur possible serait prise une et une seule fois. Chercher alors une contradiction. Variante : utiliser le principe des tiroirs (Pingeonhole) en séparant les cas où il existe un sommet de degré n-1 ou pas.

Ah pardon d'ailleurs mon argument pour (4) est non probant, il ne marche pas!!!

Bon bin je reprends la suggestion des autres: il n'y a qu'un seul sommet isolé éventuel et les n-1 autres sommets ont un degré qui appartient à $\{1;...;n-2\}$. Et si y en a pas, même genre d'argument de 3 mots.

Bonjour, pour la partie 1.
a)Travailler sur chaque composante connexe.
b) Un arc est relié à deux sommets.
c) Tous les hommes devraient ranger eux-même leurs chaussettes.
Voici une démarche pour la partie 2 :
a) Prouver qu'une chaîne non élémentaire contient un ou des cycles.
b) Déconnecter les arcs des cycles qui "conviennent" jusqu'à obtenir une chaîne élémentaire.
A propos de "l'évidence" ; cette discipline n'est toujours pas enseignée au collège ou au lycée en France bien qu'importante!.
Partie 3 : Un graphe connexe contient une chaîne maximale dont il faut compter les sommets et les arcs et puis ajouter les arcs et sommets manquants (faire une récurrence en remarquant qu'on peut toujours ajouter un arc connecté à la chaîne )
Partie 4 : Prendre une chaîne élémentaire.maximale (elle a au moins deux sommets donc...). Faire une récurrence en ajoutant les arcs qui manquent . Que se passe-t-il pour les extrémités de cette chaîne?