Induced Subgraph

An induced subgraph is a subgraph obtained from an original graph by removing a subset of vertices and/or edges together with any edges whose endpoints are both in this subset or any vertices that are their endpoints, respectively.

Note that the nonspecific term "induced subgraph" is commonly used to mean vertex-induced subgraph.

See also

Edge-Induced Subgraph, Subgraph, Vertex-Induced Subgraph

Explore with Wolfram|Alpha


Skiena, S. "Induced Subgraphs." §3.2.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 90-92, 1990.

Cite this as:

Weisstein, Eric W. "Induced Subgraph." From MathWorld--A Wolfram Web Resource.

Subject classifications