Dans toute la suite G=(S,A) désigne un graphe simple non orienté ayant n=|S| 3. Une arête a est dite incidente à un sommet s si ce sommet est une extrémité de cette arête a.
Au graphe G on associe son complémentaire et son graphe des arêtes Ga=(A,B)
Le graphe a les mêmes sommets que G et deux sommets sont adjacents dans si et seulement si ils ne le sont pas dans G : équivaut
Les sommets du graphe Ga=(A,B) sont les arêtes de G, deux sommets de Ga sont adjacents si et seulement si ils correspondent à deux arêtes de G ayant une extrémité commune (incidentes à un même sommet de G):
équivaut et équivaut et où s,s',s"
On note M(G) la matrice d'adjacence de G, L(G) matrice d'incidence de G.
Pour tout sommet de G on note son degré dans ce graphe G, on note l'ensemble des arêtes de G incidentes à ce sommet et l'ensemble des arêtes de Ga qui relient les arêtes de en tant que sommets de Ga. Pour toute arête e de F, donc sommet de Ga, on note son degré dans le graphe Ga.
Montrer que :
pour tout on a :
pour tout , on a et
Le nombre d'arête de Ga est |B|=
La matrice d'adjacence de Ga est M(Ga) où m=|A| et matrice unité
Merci de votre aide