subgraph

(definition)

Definition: A graph whose vertices and edges are subsets of another graph.

Formal Definition: A graph G'=(V', E') is a subgraph of another graph G=(V, E) iff

• V'⊆ V, and
• E'⊆ E ∧ ( (v₁, v₂)∈ E' → v₁, v₂∈ V').

Note: In general, a subgraph need not have all possible edges. If a subgraph has every possible edge, it is an induced subgraph.

Authors: PEB,AL

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 17 December 2004.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black and Alen Lovrencic, "subgraph", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/subgraph.html