Induced Subgraph (original) (raw)

TOPICS

Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology

Alphabetical Index New in MathWorld

• Discrete Mathematics
• Graph Theory
• Simple Graphs
• Miscellaneous Graphs

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 meanvertex-induced subgraph.

See also

Edge-Induced Subgraph, Subgraph, Vertex-Induced Subgraph

Explore with Wolfram|Alpha

More things to try:

• 8:5 odds, bet 97 euros
• del z e^(x^2+y^2)
• Is the golden ratio transcendental?

References

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. https://mathworld.wolfram.com/InducedSubgraph.html

Subject classifications

• Discrete Mathematics
• Graph Theory
• Simple Graphs
• Miscellaneous Graphs