Exercices (pc 7) Corrigé

Exercice 1 On a

II^{t} = D − A − A^{t}

où D est la matrice diagonale de coefficients D_{ii} = le degré du sommet i et A est la matrice d’adjacence.

Exercice 2 On raisonne par récurrence sur le nombre de faces. Si f = 1, le graphe est un arbre et le résultat est vrai puisque dans ce cas n = m + 1.

Si f > 1, on choisit une arete a sur un cycle de G. Comme un cycle sépare le plan en deux régions, l’arete a borde deux faces distinctes et on obtient le résultat par récurrence.

Sinon, chaque face est entourée par au moins 3 aretes. On obtient donc, comme chaque arete aparait sur le contour de 2 faces,

3f ≤ 2m

d’où l’inégalité m ≤ 3(n − 2).