Definition:Subgraph

Definition

A graph $H = \struct {\map V H, \map E H}$ is called a subgraph of a graph $G = \struct {\map V G, \map E G}$ if and only if $\map V H \subseteq \map V G$ and $\map E H \subseteq \map E G$.

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$.

Also see

• Results about subgraphs can be found here.

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 2.3$: Connected Graphs
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): subgraph
• 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): subgraph