Graphe partiel et sous-graphe

Soit G = (V, E) un graphe. Le graphe G' = (V, E') est un graphe partiel de G, si E' est inclus dans E. Autrement dit, on obtient G' en enlevant une ou plusieurs arêtes au graphe G.

Pour un sous-ensemble de sommets A inclus dans V, le sous-graphe de G induit par A est le graphe G = (A, E(A)) dont l'ensemble des sommets est A et l'ensemble des arêtes E(A) est formé de toutes les arêtes de G ayant leurs deux extrémités dans A. Autrement dit, on obtient G' en enlevant un ou plusieurs sommets au graphe G, ainsi que toutes les arêtes incidentes à ces sommets.

Un graphe partiel d'un sous-graphe est un sous-graphe partiel de G.
On appelle clique un sous-graphe complet de G.
On appelle stable un sous-graphe de G sans arêtes.

Le graphe G Soit G=(V, E) V={v1, v2, v3, v4, v5} E={e1=(v1,v2), e2=(v2,v3), e3=(v1,v3), e4=(v3,v4), e5=(v3,v5)}		Graphe partiel de G V'=V E'={e1, e4, e5}		Sous-graphe de G V'={v1, v3, v4, v5} E'={e3, e4, e5}		Sous-graphe partiel de G V'={v1, v2, v3, v4} E'={e1, e4}
		Une clique de G V'={v1,v2,v3} E'={e1, e2, e3}		Un stable de G V'={v1,v4,v5} E'={}

Exercice

Montrez que dans un groupe de six personnes, il y en a nécessairement trois qui se connaissent mutuellement ou trois qui ne se connaissent pas (on suppose que si A connaît B, B connaît également A).
Montrez que cela n'est plus nécessairement vrai dans un groupe de cinq personnes.

Didier Müller, 6.2.03