SÉRIE D’EXERCICES

Exercice 1 : Représenter le graphe orienté G = (X, U ) où X et U sont donnés comme

suit : X = {x, y, z, u, v} et U = {(x, y), (x, u), (z, u), (v, z)}.
Exercice 2 :

1. Déssiner et déterminer la multiplicité des deux graphes G1 = (X1 , U1 ) et G2 = (X2 , U2 )

définis comme suit :
X1 = {a, b, c, d, e, f, g} et U1 = {(a, b), (a, b), (b, e), (b, f ), (e, f ), (e, f ), (c, d), (c, d), (d, f )}
X2 = {1, 2, 3, 4, 5} et U2 = {U1 , U2 , ..., U9 }

ui u1 u2 u3 u4 u5 u6 u7 u8 u9
I(ui ) 1 2 2 3 1 3 4 5 3
T (ui ) 2 1 3 4 4 5 5 5 1
avec : I(ui ) est l’extrémité initiale de ui et T (ui ) est l’extrémité terminale de ui .

2. Déterminer le degré de chaque sommet.

Exercice 3 : Soit G = (X, U ) un graphe tel que X = {x1 , x2 , ..., x6 } et U = {u1 , u2 , ..., u9 }
et
ui u1 u2 u3 u4 u5 u6 u7 u8 u9
I(ui ) x1 x3 x2 x2 x3 x6 x4 x6 x5
T (ui ) x3 x2 x3 x3 x4 x3 x6 x6 x4
1. Représenter le graphe G = (X, U ).

2. Déterminer les degrés extérieurs et intérieurs de chaque sommet.

3. Trouver l’ensemble des voisins ΓG (A1 ), ΓG (A2 ) et ΓG (A3 ) où A1 = {x1 }; A2 = {x4 } et

A3 = {x1 , x2 }.

1
Série

Exercice 4 : Existe -t-il un graphe non orienté G = (V, E) d’ordre n = |V | = 5 qui ne

contient pas d’arêtes adjacentes tel que chaque sommet est incident à une arête.
Exercice 5 : Les suites suivantes sont elles graphiques ?

1. (2,3,4,4)

2. (9,8,6,5,3,3,3,3,1,1)

3. (1,1,1,1,1,1)

4. (5,4,4,3,3,3,1,0,0)

5. (7,6,2,2,2,1)

Exercice 6 : Soit G un graphe d’ordre 7 et de taille 10 tel qu’il contient 6 sommets de

degré d1 et un sommet de degré d2 .

1. Que valent d1 et d2 ?

2. Si G est simple, que valent d2 ?

Exercice 7 : Soit G un graphe d’ordre 12 et 14 arêtes tel que ses sommets sont de degré 2
ou 3. Combien y-a -t-il de sommets de degré 2?
n(n−1)
Exercice 8 : Montrer que si G est un graphe simple, alors |E(G)| ≤ 2
= Cn2 .
Exercice 9 : Montrer que tout graphe simple d’ordre n ≥ 2 possède au moins 2 sommets
de même degré.
Exercice 10 : Soit G = (V, E) un graphe simple d’ordre n.
2
1. Montrer que si |E(G)| > Cn−1 , alors G est connexe.
2
2. Trouver un graphe G non connexe tel que |E(G)| = Cn−1

Exercice 11 : Soit G = (V, E) un graphe simple d’ordre n.

(n−p)(n+p−1)
- Montrer que E possède au plus 2
arêtes, où p est le nombre des composantes
connexes de G.
Exercice 12 : Soit G = (V, E) un graphe à p composantes connexes. Montrer que |E| ≥
|V | − p.
Exercice 13 : En utilisant la version dictionnaire, puis la version matricielle, mettez en
ordre le graphe suivant :

Page 2
Série

2 3 4 5

1 10

6 7 8 9

Exercice 14 : Lequels des graphes suivants est un sous graphe partiel, un sous graphe
induit, un graphe partiel du graphe G?

e5 e1
e6

e4 e2
e7

e3

Exercice 15 :
Soient les deux graphes G1 et G2 respectivement :
A F 1 6

B E 2 5

C D 3 4

1. Déterminer l’ordre et la taille des graphes précédants.

2. Déterminer ses séquences de degrés.

3. G1 et G2 sont-ils isomorphes ?expliquer.

4. Supposons que deux graphes simples G et H ont le même nombre de sommets, le même
nombre d’arêtes, la même séquence de degré et aucun des deux graphes contient un
triangle. G et H sont-ills isomorphes ?

Exercice 16 : Trouver le graphe réduit du graphe suivant :

Page 3
Série

1 2 3 4 5

7 8 9 10
6

11 13 15
12 14

16 20
17 18 19

Exercice 17 : Soit G un graphe simple. Montrer que L(G) (Line graph of G) est sans K1,3
(sans griffe).
Exercice 18 : Donner un exemple d’une forêt à 13 sommets et 9 arêtes.
Exercice 19 : Soit T = (V, E) un arbre tel que chaque sommet non pendant est de degré
au moins 3. Monter que T possède deux feuilles ayant le même voisin.
Exercice 20 : Soit T un arbre d’ordre n tel que tout sommet de V est de degré au plus 5.
On construit un arbre T ∗ = (V ∗ , E ∗ ) à partir de T en ajoutant des nouveaux sommets qu’on
relie aux sommets de V de manière que tout nouveau sommet soit de degré 1 et tout sommet
de V soit de degré exactement 5. Quel est le nombre de sommets ajoutés ?
Exercice 21 : Trouver un arbre du poids minimum (APM) des deux graphes suivants :

5 6
C D E

5 10
6 14
8
8 A B 10
6 10
15 8
H G F
12 12

Figure 0.1: G1

Page 4
Série

4
B C

1 8

A 2 6 D
5

3 9
F E
7

Figure 0.2: G2
Exercice 22 : Soit T1 = (V1 , E1 ),T2 = (V2 , E2 ) deux arbres couvrants d’un graphe G tel que
E1 ∩ E2 = φ. Montrer que ∀u ∈ E1 , ∃v ∈ E2 tel que T − u + v est un arbre.
Exercice 23 : Montrer que le graphe suivant est planaire :
1

6 7 2

10

9 8

5 4 3

Exercice 24 : Montrer par deux méthodes différentes que le graphe suivant n’est pas planaire :
1

4 3

6 5

Exercice 25 : Soit G un graphe simple connexe planaire d’ordre moins de 12 sommets. Montrer
que G possède un sommet de degré au plus 4.

Page 5
Série

Exercice 26 : Soit G un graphe simple connexe planaire de taille mois de 30 arêtes. Monter
que G possède un sommet de degré au plus 4.
Exercice 27 : Soit G un graphe connexe simple d’ordre au moins 11. Monter que si G est
connexe, alors G où G est non planaire (G est le graphe complémentaire de G).
Exercice 28 : Soit G = (X, U ) le graphe suivant.

e2
2 5
e1 e8 e3
1 e7 e10 6
e6 e9 e4
3 4
e5

Déterminer 3 cycles et 3 cocycles de V et trouver leurs vecteur représentatif.

Exercice 29 : Soit G = (X, U ) le graphe orienté suivant.

e1 e4

a e3 d

e5
e2

Vérifier le Lemme de minty pour l’arc u = e1 ensuite pour l’arc u = e5 .

Exercice 30 : Soit G = (X, U ) le graphe orienté suivant.

u7
1 2

u8 u6 u2 u1

d u5 3

5 u9 u3

u4

Vérifier le lemme de minty pour l’arc u1 .

Exercice 31 : Déterminer α(G) pour les graphes suivants :

Page 6
Série

1 u

1 2 2
2 x v x
5 v
2 x
1 v x

1 u y
3 4 z v
3 4 z v
3 4 z v
3

C3 C4 C5 K4

Page 7
Série

n
Exercice 32 : Montrer que tout graphe G satisfait α(G) > ∆(G)+1
.

Page 8