Subgrafos

---

Um grafo $H$ é um subgrafo de um grafo $G$ se:

• O conjunto de vértices de $H$ for um subconjunto do conjunto de vértices de $G$: $V(H)\subseteq V(G)$
• O conjunto de arestas de $H$ for um subconjunto do conjunto de arestas de $G$: $E(H)\subseteq E(G)$

Mas de forma simplificada, um subgrafo é uma parte de um grafo maior.

Exemplo

$H$ é subgrafo próprio de $G$ ou $H\subset G$.

NOTE

Um subgrafo $H$ é considerado “próprio” se ele for um subgrafo de $G$, mas não for idêntico a $G$.

Referências

---

Teoria dos grafos - Subgrafos, passeios, trilhas e caminhos