De fois il nous intéresse seulement un groupe de sommets dans l’ensemble total d’un graphe. Les sous graphes sont le résultat de supprimer les sommets et les arêtes qui ne connectent pas les sommets qui nous intéressent. On obtient alors un graphe plus réduit que l’original, lequel contiendrait seulement les points qu’on veut. On dira que c’est un sous-graphe du graphe original.

 

Alors pour trouver un sous graphe il faut simplement délimiter l’ensemble d'arêtes qu’on veut étudier et éliminer le reste de parties du graphe originel. Donc le sous graphe sera formé par quelques arêtes et sommets du graphe originel. 

 

Un autre point important c’est que le degré du sommet appartenant aux deux graphes sera inférieur. Donc soit G le graphe primaire et H le sous graphe, et donc le sommet AV(H) et V(G), alors grH(A)grG(A) 

 

Dans l’exemple suivant on verra comme on peut trouver un sous graphe.Ce graphe G on peut le définir comme G=(V,E), où:

​

•  V=[A,B,C,D,E] et #V=5

• E=[AB,BE,ED,EC,DC,DA,CA] et #E=7

​

​

Il faut mentionner que chaque graphe n’a pas strictement seulement un sous graphe, sinon il peut en avoir plusieurs. Dans cet exemple on peut trouver deux sous graphes:

 

Le premier sous graphe H1 est formé par:

• V=[A,C,D] et #V=3

• E=[AC,CD,DA] et #E=3

Degrés:

grA(H1)=2< grA(G)=3

grC(H1)=2<grC(G)=3

grD(H1)=2<grD(G)=3

 

Le deuxième sous graphe H2est formé par:

• V=[E,C,D] et #V=3

• E=[ED,DC,CE] et #E=3

Degrés:

grC(H2)=2< grD(G)=3

grD(H2)=2<grD(G)=3

grE(H2)=2<grD(G)=3

​