Combinatoire et Graphes Université Pierre et Marie Curie
LM226 B. Girard 2011–2012
Corrigé (2ème session)
Solution 1.
1. D’après le théorème d’Havel et Hakimi, on a les équivalences suivantes.
(6, 5, 4, 2, 2, 2, 1) graphique ⇐⇒ (4, 3, 1, 1, 1, 0) graphique
⇐⇒ (2, 0, 0, 0, 0) graphique,
mais (2, 0, 0, 0, 0) ne peut pas être une suite graphique. On en déduit donc qu’il
n’existe pas de graphe simple dont la suite des degrés soit (6, 5, 4, 2, 2, 2, 1).
2. Soit G = (S, A) un graphe simple dont la suite des degrés soit (4, 4, 4, 3, 3, 2, 2).
Alors, il existe deux sommets distincts de degré 4 qui sont voisins dans G, car
sinon, chacun des trois sommets de degré 4 serait relié aux deux sommets de degré
3 et aux deux sommets de degré 2, d’où δ(G) ≥ 3, ce qui est une contradiction.
De plus, si s et t sont deux sommets distincts de degré 4 voisins dans G, alors en
notant Γ(s) (resp. Γ(t)) l’ensemble des voisins de s (resp. de t) dans G, on obtient
|Γ(s) ∩ Γ(t)| = |Γ(s)| + |Γ(t)| − |Γ(s) ∪ Γ(t)| ≥ d(s) + d(t) − |S| = 1.
Ainsi, s et t possèdent un voisin commun, et le graphe G doit contenir un triangle.
Solution 2.
Soit G = (S, A) le graphe simple dont les sommets sont les six films proposés, et dans
lequel deux films sont reliés par une arête si et seulement s’il existe une personne inscrite
pour ces deux films. Voici une représentation du graphe G.
a
f b
e c
Le nombre recherché est donc χ(G). D’un côté, comme G contient K4 , on a χ(G) ≥
χ(K4 ) = 4. D’un autre côté, en prenant les sommets dans l’ordre alphabétique, l’algo-
rithme glouton nous permet de trouver une 4-coloration de G.
1
a (1)
f (4) b (2)
e (3) c (1)
d (2)
Ainsi, le nombre minimal d’horaires que le ciné-club doit prévoir afin que chaque membre
puisse assister à toutes les projections auxquelles il s’est inscrit est χ(G) = 4. De plus,
les classes de couleurs ci-dessus nous donnent une programmation possible des six films
proposés. En effet, il suffit de projeter les films a et c à un premier horaire, les films b et
d à un deuxième horaire, le film e à un troisième et le film f à un quatrième.
Solution 3.
1. D’après le lemme des poignées de mains, on a 3n = 2m = 2(2n − 3), ce qui entraîne
n = 6 et m = 9.
2. Les deux graphes simples ci-dessous vérifient bien les conditions de l’énoncé
et ne sont pas isomorphes, car l’un ne contient pas de triangle mais l’autre si.
Solution 4.
1. Pour tout n ≥ 1, on notera An l’ensemble des mots de n lettres sur l’alphabet
{a, b, c} dans lesquels la lettre a n’apparaît jamais deux fois consécutives. Pour
n = 1, on a clairement A1 = {a, b, c}, d’où a1 = 3. Pour n = 2, on a A2 =
{ab, ac, ba, bb, bc, ca, cb, cc}, et a2 = 8.
2. Pour n = 0, le résultat de la question 1 nous donne bien l’égalité a2 = 2(a1 + a0 ).
Maintenant, supposons n ≥ 1. Parmi les mots de An+2 , il y en a an se terminant
par ba, an se terminant par ca, an+1 se terminant par b et an+1 se terminant par c.
Ainsi, le principe d’addition entraîne
an+2 = 2(an+1 + an ),
ce qui est le résultat souhaité.
2
3. On a la chaîne d’égalités suivante.
X
A(X) = an X n
n≥0
X
= a0 + a1 X + an X n
n≥2
X
= a0 + a1 X + an+2 X n+2
n≥0
X
= a0 + a1 X + 2 (an+1 + an ) X n+2
n≥0
X X
= a0 + a1 X + 2X an+1 X n+1 + 2X 2 an X n
n≥0 n≥0
2
= a0 + a1 X + 2X (A(X) − a0 ) + 2X A(X)
= 1 + X + 2XA(X) + 2X 2 A(X).
On en déduit donc que
1+X
A(X) = .
1 − 2X − 2X 2
√ √
4. En posant α = (1 + 3) et β = (1 − 3), on a
1+X
A(X) =
(1 − αX)(1 − βX)
√ ! √ !
3+2 1 3−2 1
= √ + √
2 3 1 − αX 2 3 1 − βX
√ ! √ ! !
X 3+2 n 3−2
= √ α + √ β n X n.
n≥0
2 3 2 3
Ainsi, on obtient
√ ! √ !
3+2 √ 3−2 √ n
an = √ (1 + 3)n + √ (1 − 3) .
2 3 2 3
