Inscription / Connexion Nouveau Sujet
Niveau LicenceMaths 2e/3e a
Partager :

Un peu de graphe

Posté par
maxmaths65
22-01-19 à 22:48

Bonjour,
Je vous présente dans un premier temps le sujet de mon exo :

Soient u et v deux sommets adjacents d'un graphe G d'ordre n (il a n sommets au total).
Montrons que l'arrete (u,v) appartient à au moins d(u)+d(v)-n triangles (ou 3-cycles).

Comment ai-je lancé les choses ?

Tout d'abord, je compte le nombre de voisins de u  : il y en a au plus n-1, idem pour v.
Reste a voir combien de ces voisins sont communs à u et à v (donc qui ne sont pas non plus u et v), mais je ne sais pas comment faire de liens.....

Merci

Posté par
jarod128
re : Un peu de graphe 23-01-19 à 00:56

Bonjour,
Que penses tu d'une récurrence sur n?



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1455 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !