Subgraph

Topics: Graph Theory - Graph

---

(definition)

A graph $g$ is a subgraph of another graph $G$ when:

• All of the vertices of $g$ are contained in $G$.
• Every edge in $g$ has the same terminal vertices in $G$.

Exact Same Vertices and Edge Connections

Beware! For a graph to be a subgraph of another one, it must have the exact same vertices and edge connections, letter representation and all.

Subgraphs can be edge-disjoint or vertex-disjoint.

Theorems §

(theorem)

• A graph is a subgraph of itself
• A subgraph of a subgraph of $G$ is also a subgraph of $G$ (transitivity)
• A single vertex of $G$ is a subgraph
• An edge with its terminal vertices (in $G$) is a subgraph of $G$

Edge-Disjoint Subgraphs