Um sub­grafo de um grafo é uma parte do grafo.  Embora esse conceito seja intuitivo, sua formulação rigorosa exige cuidado. Formularmos o conceito como uma relação entre dois grafos.

Um grafo H é sub­grafo de um grafo G se todo vértice de H é vértice de G  e  todo arco de H é arco de G.

Alguns tipos de sub­grafos merecem destaque:

• Um sub­grafo de um grafo G é gerador  (= spanning)  se contém todos os vértices de G.
• Um sub­grafo H de um grafo G é  induzido  se todo arco de G que tem ambas as pontas em H também é arco de H.
• Um sub­grafo de um grafo G é próprio se for diferente de G.

Dado um conjunto X de vértices de um grafo G, o sub­grafo de G  induzido por X  é o sub­grafo formado por X e por todos os arcos de G que têm ambas as pontas em X.

Subgrafos

Um sub­grafo de um grafo não-dirigido não é necessariamente não-dirigido.  Portanto, um sub­grafo de um grafo não-dirigido não é necessariamente não-dirigido. Portanto, a seguinte definição não é redundante.

Um sub­grafo (= subgraph) não-dirigido de um grafo não-dirigido G é qualquer grafo H que seja sub­grafo de G.

Subgrafos e nossas estruturas de dados

Infelizmente, nossas estruturas de dados entram em choque com a definição de sub­grafo, pois supõem que todo grafo tem vértices 0 1 2 ... V-1.  Assim, será necessário empregar um certo jogo de cintura ao usar o termo sub­grafo:  se G é um grafo com vértices 0 1 2 ... 99 e dissermos que H é um sub­grafo de G e tem 5 vértices, ficará subentendido que os vértices de H não são necessariamente  0 1 2 3 4,  mas podem ser  2 4 6 50 99  ou  10 20 30 40 50,  por exemplo.