TOPICS
Search

Subgraph


A subgraph G^' of a graph G is a graph G^' whose vertex set and edge set are subsets of those of G. If G^' is a subgraph of G, then G is said to be a supergraph of G^' (Harary 1994, p. 11).

A vertex-induced subgraph, often simply called "an induced subgraph" (e.g., Harary 1994, p. 11) of G induced by the vertex set V (where V is a subset of the vertex set of G) is the graph G^' with vertex set V and edge set consisting of those edges both of whose endpoints are in V.


See also

Edge-Induced Subgraph, Forbidden Subgraph, Graph, Induced Subgraph, Supergraph, Subtree, Ulam's Conjecture, Vertex-Induced Subgraph

Explore with Wolfram|Alpha

References

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 11, 1994.

Referenced on Wolfram|Alpha

Subgraph

Cite this as:

Weisstein, Eric W. "Subgraph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Subgraph.html

Subject classifications