Definition:Subgraph
From ProofWiki
Definition
A graph $H = \left({V \left({H}\right), E \left({H}\right)}\right)$ is called a subgraph of a graph $G = \left({V \left({G}\right), E \left({G}\right)}\right)$ if $V \left({H}\right)\subseteq V \left({G}\right)$ and $E \left({H}\right)\subseteq E \left({G}\right)$.
That is to say, it contains no vertices or edges that are not in the original graph.
If $H$ is a subgraph of $G$, then:
- $G$ contains $H$;
- $H$ is contained in $G$
Embedding
If a graph $F$ is isomorphic to a subgraph $H$ of $G$, then $F$ can be embedded in $G$.
Sources
- Gary Chartrand: Introductory Graph Theory (1977): $\S 2.3$
